1. 개요

조합최적화 문제의 일종이다. 한정된 가방의 무게 W안에서 가치가 최대가 되도록 아이템들의 부분집합을 찾는 문제이다.
'분할 가능한 배낭'과 '분할 가능하지 않은 배낭' 문제로 구분된다. 후자는 흔히 '0-1 배낭 문제'로 표현된다.

2. 0-1 배낭문제

0-1 배낭문제 (0-1 Knapsack Problem)는 동적계획법, 백트래킹 등의 조합 최적화 문제 풀이의 방법을 사용해야 한다.

동적계획법을 이용한 풀이

def knapsack2(i, W, w, p):
    if (i <= 0 or W <= 0):
        return 0
    if (w[i] > W):
        value = knapsack2(i - 1, W, w, p)
        print(i - 1, W, value)
        return value
    else: # w[i] <= W
        left = knapsack2(i - 1, W, w, p)
        print(i - 1, W, left)
        right = knapsack2(i - 1, W - w[i], w, p)
        print(i - 1, W - w[i], right)
        return max(left, p[i] + right)

출처 : https://namu.wiki/w/%EB%B0%B0%EB%82%AD%20%EB%AC%B8%EC%A0%9C