[고급 알고리즘] 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[K+1];

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

• DP[v] :총 v 무게로 채웠을 때 최대 가치

 

 

출처

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