0/1 배낭 문제

정의

각 항목이 무게 $w_i$와 가치 $v_i$를 가질 때, $\sum w_i x_i \le C$를 지키며 $\sum v_i x_i$를 최대화하도록 $x_i \in \{0,1\}$를 선택한다.

예시

용량 $C = 10$인 배낭과 네 개의 항목이 있다고 하자.

항목	무게 $w_i$	가치 $v_i$
1	5	10
2	4	7
3	6	9
4	3	4

무게 합이 10을 넘지 않는 부분집합 중 가치 합이 가장 큰 것은 항목 $\{1, 2\}$로, 무게 $5 + 4 = 9 \le 10$, 가치 $10 + 7 = 17$이다. 흥미롭게도 항목 $\{2, 3\}$은 무게 $4 + 6 = 10$으로 용량을 꽉 채우지만 가치는 $16$에 그친다 — 용량을 더 채운다고 해가 더 좋아지는 것은 아니다.

왜 여기 있나

배낭 문제는 절단·적재와 두 가지로 얽힌다: (1) 동적 계획법이라는 공통 방법, (2) 1D 절단 재고의 열 생성에서 가격 산정 부분문제가 곧 배낭 문제다.

관련 노드

아래 깊이 1 그래프를 참고하라.