[고급 알고리즘] Dynamic Programming: Knapsack Problem

1.  Knapsack Problem (배낭 문제)

• 베낭에 담을 수 있는 최대 무게가 정해져 있고, 가치와 무게가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 짐 채우기

 

0-1 Knapsack Problem

• 각 짐을 한 번만 선택할 수 있음
• 각 짐을 넣거나 넣지 않는 선택을 할 수 있음

 

점화식

• $m[0, w] = 0$
• $m[i, w] = m[i-1, w] \quad \text{if } w_{i} > w$
• $m[i, w] = \max(m[i-1, w], m[i-1, w-w_{i}] + v_{i}) \quad \text{if } w_{i} \leqslant w$

 

2. 풀이

코드

costs = new int[N+1];
volumes = new int[N+1];

dp = new int[N+1][K+1];

for (int item = 1; item <= N; item++) {
    for (int volume = 1; volume <= K; volume++) {
        int V = volumes[item], C = costs[item];
        
        if (volume>=V) dp[item][volume] = Math.max(dp[item-1][volume], dp[item-1][volume-V]+C);
        else dp[item][volume] = dp[item-1][volume];         		
    }
}

• DP[i][w] : i번째 보석까지 w의 무게로 채웠을 때 최대 가치
• DP[i][w] = max(i번째 보석 채우기 + 남은 무게로 보석 채우기, i-1번째 보석으로 채우기)

 

 

 

출처

• Wiki - Knapsack problem
• 메시에 - Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem)