배낭 문제

일반적으로 배낭문제는

정해진 무게 안에 가장 가치 있는 물건을 고르는 것 이다.

 

이번 포스팅에서는 배낭 문제의 3가지 유형 (0/1, 무한, 개수제한)에 대해 이해해보려한다.

사실 배낭문제도 2차원 배열을 활용한 DP 문제다

 

따라서 제일 먼저 문제를 보고 할 일은 

최적 부분 구조 + 부분 반복 문제 확인하는 것이다. 

 

 

이전 상태 유지 + 개수 제한 일 때는 중복 사용 방지를 위해 2차원 배열을 사용이 유리할 수 있다.

 

개수제한일 때를 생각해보면 1차원 배열 사용시 

중복 사용될 가능성이 있다. 

 

제한이 2개일때 

배낭 무게 최대 무게 6

아이템 1개에 대하여 무게 2, 가치 10 이라하면

dp = {0, 0, 10, 0, 20, 0, 30} 이런식으로 3번 같은 아이템을 사용해 버린다. 

때문에 2차원 배열로 같은 아이템의 제한 초과 중복 연산을 막아야한다. 

 

역방향을  하면 되지 않나 싶지만 중복 사용이 불가능 하기에 (한 아이템 여러번 참조 불가)

결국에는 2차원 배열로 해야한다. 

0/1 Knapsack

물건을 최대 1번만 선택 가능

물건을 넣는다 (1), 안 넣는다 (0) 

 

점화식

2차원

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

 

 

1차원

최적화시 역방향 순회를 해야 같은 물건 중복 사용을 하지 않는다. 

for (int i = 1; i <= N; i++) {
    for (j = W; w[i] >= j; j--) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

 

---

Unbounded Knapsack (무한)

각각의 물건을 무제한 선택 가능

필요한 만큼 넣는다.

 

점화식

2차원

                         // 중복 아이템 가능하기에 i로 유지 
dp[i][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);

 

1차원 

for (int i = 1; i <= N; i++) {
    // 중복 가능이기에 정방향 탐색
    for (j = w[i]; j <= W; j++) { 
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

---

Bounded Knapsack (개수 제한)

각 물건을 최대 k번까지 사용 가능

점화식

2차원

for (int i = 1; i <= N; i++) {
    for (int j = 0; j <= K; j++) {
        dp[i][j] = dp[i - 1][j]; // i번 아이템을 아예 안 쓰는 경우

        for (int k = 1; k <= count[i]; k++) {
            int totalWeight = k * weight[i];
            int totalValue = k * value[i];

            if (j >= totalWeight) {
                dp[i][j] = Math.max(dp[i][j],
                                    dp[i - 1][j - totalWeight] + totalValue);
            } else break;
        }
    }
}

 

1차원

for (int i = 1; i <= N; i++) { // i번째 아이템
    for (int j = W; j >= 0; j--) { // 현재 배낭 용량
        for (int k = 1; k <= count[i]; k++) { // 해당 아이템을 k개까지 사용할 수 있음
            int totalWeight = k * weight[i];
            int totalValue = k * value[i];

            if (j >= totalWeight) {
                dp[j] = Math.max(dp[j], dp[j - totalWeight] + totalValue);
            } else {
                break; // 더 넣을 수 없음 → k 증가시키는 건 무의미
            }
        }
    }
}