0/1 배낭 문제

문제

도둑이 보석 가게에 들어갔다. 배낭에는 무게가 W 이하인 물건만 담을 수 있다. 가게에는 N개의 물건이 있고, 각 물건에는 무게 w와 가치 v가 매겨져 있다. 각 물건은 가져가거나(1) 가져가지 않거나(0) 둘 중 하나만 선택할 수 있다. 같은 물건을 여러 개 가져갈 수는 없다.

배낭에 담을 수 있는 물건들의 가치 합의 최댓값을 구하시오.

풀이 힌트

물건 i까지 봤을 때 무게 한도 w에서 얻을 수 있는 최대 가치를 dp[i][w]라고 하면:

• 물건 i를 담지 않는다: dp[i-1][w]
• 물건 i를 담는다 (무게가 허락할 때): dp[i-1][w - w_i] + v_i

둘 중 더 큰 값을 고르면 된다. 즉,

dp[i][w] = max(dp[i-1][w], dp[i-1][w - w_i] + v_i)

재귀 + 메모이제이션으로 풀 수도 있고, 반복문으로 테이블을 채워 나갈 수도 있다. 재귀만 쓰면 같은 부분 문제를 여러 번 다시 풀게 되어 매우 느려진다.