0 - 1Knapsack Problem 쪼갤 수 없는 물건을 배낭에 담는문제로 DP로 풀어야하는 대표적인 문제 DP로 풀수 있는지 여부는 Principle of Optimality 성립 여부를 보면 된다. Principle of Optimality 어떤 문제의 입력 사례의 최적해가 그 입력 사례를 분할한 부분사례에 대한 최적해를 항상 포함하고 있으면, 그 문제에 대하여 최적의 원리가 성립한다 즉 부분사례의 최적해가 현 사례의 최적해의 부품이 된다면 DP로 풀 수 있다. 물건을 취하지 않고 P[i-1][j]를 선택하느냐 취하고 P[i-1][j-wk] + v[i]를 하느냐. 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 13 13 2 0 0 0 0 8 8 13 13 3..