Unbounded Knapsack Problem(갯수 제한없는 배낭문제)

무게와 가격이 각각 Wi, Vi인 n개의 물건이 있습니다. 이 물건들로부터 무게의 총합이 W를 초과하지 않도록 선택했을 때의 가격 총합의 최대치를 구하세요. 단 같은 종류의 물건을 몇 개라도 고르는 것이 가능합니다.

 

일반적인 배낭문제를 생각하고 점화식을 정의하면 아래와 같다.

dp[i + 1][j] = i번까지 물건 무게의 총합이 j 이하가 되도록 골랐을 때 가치의 최대치

dp[i][0] = dp[0][j] = 0

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

 

이와 같은 점화식으로 코드를 구현하면 아래와 같다

 

int dp[MAX_N + 1][MAX_W + 1];

 

void solve() {

  for(int i = 0; i < N; ++i)

    for(int j = 0; j <= W; ++j)

      for(int k = 0; k * w[i] <= j; ++k){

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

  cout << dp[i + 1][W] << endl;

 

위와 같은 루프는 3중 루프를 돌고 최악의 경우 시간복잡도가 O(NW^2)가 된다.

그러므로 제한시간 내에 모든 케이스를 해결하기가 히든 코드일 가능성이 높다.

 

위의 점화식을 DP테이블로 만들어보면 아래와 같다.

N = 3

(w, v) = {(3, 4), (4, 5), (2, 3)}

W = 7

dp[i][j]

i / j	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	4	4	4	8	8
2	0	0	0	4	5	5	8	9
3	0	0	3	4	5	7	8	10

여기서 dp[3][7] = max(dp[2][7 - 2] + 3, dp[2][7 - 2 * 2] + 3 * 2, ... , dp[2][7 - 2 * k] + 3 * k) 이다.

하지만 우리는 dp[2][7]를 구할때 이미 dp[2][7 - 2] + 3을 제외한 나머지의 최대치를 구한 상태이다. 결론적으로는

dp[3][7] = max(dp[3][7], max[2][7 - w[2]] + v[2])

가 된다. 이를 수식으로 나타내면 아래와 같다.

dp[i + 1][j] = max(dp[i][j - w[i] * k] + v[i] * k) (k >= 0)  (1)

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

  = max(dp[i][j], dp[i](j - w[i]) - w[i] * k] + v[i] * k + v[i] (k >= 0)

  = max(dp[i][j], dp[i][j - w[i]] + v[i])  // (1)을 이용하여 치환함

이같은 점화식을 이용한다면 O(NW)만에 문제를 해결할 수 있다.

 

int dp[N_MAX + 1][W_MAX + 1];

 

void solve(){

  for(int i = 0; i < N; ++i)

    for(int j = 0; j <= W; ++j)

if(j < w[i])

  dp[i + 1][j] = dp[i][j];

      else

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

  cout << dp[N][W] << endl;

}