[DP] 0-1 배낭

문제

물건 $N$개가 있고 $i$번 물건은 무게 $w_i$, 가치 $v_i$이다. 각 물건은 한 번만 담을 수 있다. 무게 합이 용량 $W$를 넘지 않게 담아 가치 합을 최대로 하라.

접근

$dp[c]$를 "용량 $c$를 쓸 때의 최대 가치"라 하면, 물건 하나를 담을지 말지 정한다.

$dp[c] = \max\bigl(dp[c], \; dp[c - w_i] + v_i\bigr)$

각 물건을 한 번만 쓰려면 안쪽 반복문에서 용량 $c$를 큰 쪽에서 작은 쪽으로 내려가며 갱신해야 한다.

입출력 예시

입력:
3 5
2 3
3 4
4 5
출력: 7