배낭 문제

배낭 문제 배낭 문제란 버틸 수 있는 무게가 정해져 있는 배낭이 있고, 일정한 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 하는 방법을 찾는 문제이다. 배낭 문제는 짐을 쪼갤 수 있는 경우(Fractional)와 없는 경우(0-1)로 구분된다. 쪼갤 수 있는 경우는 무게당 가치가 높은 물건부터 그리디하게 넣으면 $O(N)$만에 해결할 수 있다. 쪼갤 수 없는 경우는 다항 시간에 해결이 불가능하며, 다이나믹 프로그래밍이나 백트래킹과 같은 방법을 적용해야 한다. 이 글에서는 다이나믹 프로그래밍을 이용해 0-1 배낭 문제를 해결해보려고 한다. 점화식 세우기 $i$번째 짐까지 고려했을 때, 무게 제한이 $j$인 배낭에 담을 수 있는 최대 가치를 $f(i, j)$라고 하자. 각 짐을 고..