배낭(Knapsack) 문제, 다이나믹 프로그래밍 해법 배우기

1. 배낭 문제 개요 n개의 물건이 존재하고, 각 물건 i의 무게는 $w_{i}$, 가치가 $v_{i}$로 주어진다. 배낭의 용량이 W라고 할때, 이러한 배낭에 담을 수 있는 물건의 최대 가치는? 단, 배낭에 담은 물건의 무게 합은 W를 초과할 수 없고 각각의 물건은 1개씩만 존재한다 그리고 물건을 쪼개서 담을 수 없다고 가정한다. 이러한 문제는 0-1 knapsack 문제라 부르고 물건을 쪼개서 담을 수 있는 경우도 물론 있는데 fractional knapsack 문제라고 부른다. 2. 해법 - 완전탐색 조금 생각해보면, 존재하는 물건들의 집합 S에서, 일부를 골라 가방에 담는 문제이므로, 집합 S에서 모든 부분집합을 구하고, 가치들의 합을 조사한다 이때, 가방의 용량을 넘지 않으면 가치의 합을 구하고..