0/1 Knapsack Problem이란? 용량이 W인 배낭, N개의 물건(각 물건은 무게(w)와 가치(v)가 주어짐) 1. 배낭에 담을 물건의 무게의 합이 W를 초과하지 않으면서 2. 담을 수 있는 최대 가치를 찾는다. 물건을 쪼갤 수 있다면 > Fraction Knapsack Problem 물건을 쪼갤 수 없다면 > 0/1 Knapsack Problem 접근법 DP 중에서도 작은 문제의 해로 큰 문제의 해를 찾는 상향식 접근법을 사용한다. 그렇다면 점화식을 구해야 한다. 부분 문제를 정의해 보면, 물건을 담을 수 있는 경우와 담을 수 없는 경우로 나눌 수 있고 담을 수 있는 경우에는 물건을 넣기로 결정하거나 물건을 안 넣기로 결정하는 경우로 또 나눌 수 있다. 정리하면, 1. 물..
