DP - Knapsack(배낭 문제)
관련 문제:
백준 12865번 - 평범한 배낭 https://www.acmicpc.net/problem/12865
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
물건의 무게(W)와 가치(V)가 주어질 때, 정해진 무게 안으로 물건을 택하면서 얻을 수 있는 최대 가치를 구하는 것이다.
풀이:
DP(i, W) = i번째 물건까지 있고 무게 제한이 W일 때의 최대 가치
이 경우 DP(i, W) = { DP(i-1, W) (if Wi > W)
max[DP(i-1, W-Wi) + Vi, DP(i-1, W)] (if Wi <= W) 이다.
해설:
1) "DP(i-1, W) (if Wi>W)"의 의미
i번째 물건의 무게인 Wi가 무게 제한인 W보다 크니까 당연히 택할 수 없다. 그러므로 i-1번째 물건까지 택했을 때의 최대 가치였던 DP(i-1, W)가 DP(i, W)이다.
2) "max[DP(i-1, W-Wi) + Vi, DP(i-1, W)] (if Wi <= W)"의 의미
i번째 물건의 무게인 Wi가 무게 제한인 W보다 작거나 같으므로 택할 가능성이 있다.
- 만약 택했다면, 일단 택한 후의 무게가 W를 넘지 않아야 하므로 i-1번째 물건까지 있을 때 선택한 결과가 W-Wi보다 작거나 같았어야 한다. 결론적으로 DP(i, W)의 후보 중 하나는 DP(i-1, W-Wi)+Vi이다.
- 만약 택하지 않았다면, i -1번째 물건까지 택했을 때의 최대 가치인 DP(i-1, W)가 또 다른 DP(i, W)의 후보이다.
종합하면 택할 가능성이 있을 때의 가치의 최댓값인 DP(i, W)는 max[DP(i-1, W-Wi) + Vi, DP(i-1, W)]이다.
Pseudocode:
N = 물건 개수;
K = 무게 제한;
DP[N+1][K+1]; //[0][x]와 [x][0]은 모두 0으로 초기화할 것. DP[i][w]는 위의 설명에서 DP(i, W) 값을 의미함.
item[N+1]; //각 원소는 무게, 가치 두가지 정보를 가지고 있음
for (i = 1 ~ N) {
for (w = 1 ~ K) {
if (item[i].무게 > w) DP[i][w] = DP[i-1][w];
else DP[i][w] = max(DP[i-1][w - item[i].무게] + item[i].가치, //"w - item[i].무게"가 배열 범위 안 벗어나게 조심
DP[i-1][w]);
}
}
구하려는 최대 가치 = DP[N][K];