문제 정의

무게 제한이 있는 배낭과 여러 개의 아이템이 주어졌을 때, 각 아이템은 고유한 무게와 가치를 가집니다. 한 번에 하나의 아이템만 선택할 수 있으며, 배낭의 총 무게가 허용 범위를 넘지 않도록 하면서 담을 수 있는 아이템들의 총 가치를 최대화하는 것이 목표입니다.

예시:

• 아이템 개수: 3개
• 각 아이템의 무게: [1, 3, 4]
• 각 아이템의 가치: [15, 20, 30]
• 배낭의 최대 수용 가능 무게: 4

이 경우, 최적의 조합은 첫 번째(무게 1, 가치 15)와 두 번째(무게 3, 가치 20) 아이템을 선택하는 것으로, 총 가치는 35가 됩니다.

동적 계획법을 이용한 점화식 도출

이 문제는 2차원 DP 테이블을 활용하여 해결할 수 있습니다. 여기서 dp[i][j]는 처음 i개의 아이템 중에서 선택하여, 배낭의 용량이 j일 때 얻을 수 있는 최대 가치를 의미합니다.

테이블의 초기 상태는 다음과 같습니다 (행: 아이템 인덱스, 열: 배낭 용량):

각 상태 전이는 다음 두 가지 경우를 비교하여 결정됩니다:

1. 현재 아이템을 포함하지 않을 때: 이전 상태의 최대 가치를 유지합니다 → dp[i-1][j]
2. 현재 아이템을 포함할 수 있을 때: 남은 용량 j - weight[i-1]에서의 최대 가치에 현재 아이템의 가치를 더함 → dp[i-1][j - weight[i-1]] + value[i-1]

따라서 상태 전이 방정식은 다음과 같습니다:

dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i-1]] + value[i-1])

구현 코드

public class ZeroOneKnapsack {
    public static void main(String[] args) {
        int capacity = 4;
        int[] weights = {1, 3, 4};
        int[] values = {15, 20, 30};
        int itemCount = weights.length;

        // DP 테이블 초기화
        int[][] dp = new int[itemCount + 1][capacity + 1];

        // 테이블 채우기
        for (int i = 1; i <= itemCount; i++) {
            for (int j = 1; j <= capacity; j++) {
                int currentWeight = weights[i - 1];
                int currentValue = values[i - 1];

                if (currentWeight > j) {
                    // 아이템을 담을 수 없음
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 포함 여부에 따른 최대값 선택
                    int exclude = dp[i - 1][j];
                    int include = dp[i - 1][j - currentWeight] + currentValue;
                    dp[i][j] = Math.max(exclude, include);
                }
            }
        }

        System.out.println("최대 가치: " + dp[itemCount][capacity]);

        // DP 테이블 출력
        for (int i = 0; i <= itemCount; i++) {
            for (int j = 0; j <= capacity; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println();
        }
    }
}

선택된 아이템 추적하기

최적해를 구성하는 실제 아이템들을 찾기 위해선, 완성된 DP 테이블을 역추적해야 합니다. 아래 코드는 어떤 아이템들이 배낭에 포함되었는지를 출력합니다:

// DP 테이블 끝에서부터 거꾸로 탐색
int remainingCapacity = capacity;
for (int i = itemCount; i > 0; i--) {
    // 현재 값이 직전 행과 다르면, 해당 아이템이 포함된 것
    if (dp[i][remainingCapacity] != dp[i - 1][remainingCapacity]) {
        System.out.println("선택된 아이템: " + i + "번 (무게: " + weights[i-1] + ", 가치: " + values[i-1] + ")");
        remainingCapacity -= weights[i - 1]; // 사용된 용량 차감
    }
}

이 방식은 각 단계에서 아이템이 실제로 추가되었는지를 판단하고, 그에 따라 남은 용량을 갱신하며 역으로 경로를 복원합니다.