홍라이프 계산기0/1 배낭 문제 풀이 쉽게 이해하기 — 개념과 원리
0/1 배낭 문제는 무게와 가치가 있는 물건들과 무게 제한이 있는 배낭이 주어질 때, 어떤 물건을 넣어야 가치의 합이 가장 큰지 묻는 문제입니다. 물건은 통째로 넣거나 넣지 않거나 둘 중 하나입니다. 예산 배분, 자원 한도 안에서 사업 고르기, 화물 적재 같은 문제가 같은 구조를 가집니다. 이 계산기는 동적 계획법으로 정확한 최적해를 구합니다.
계산 방법
D[i][c]를 앞의 i개 물건만 써서 용량 c로 얻는 최대 가치라고 합니다.
- D[0][c] = 0입니다.
- D[i][c] = D[i−1][c](i번째를 넣지 않음)이고, wᵢ ≤ c이면 max(D[i−1][c], D[i−1][c − wᵢ] + vᵢ)(넣음)입니다.
- 최대 가치는 D[n][용량]입니다.
고른 물건은 거꾸로 따라가며 D[i][c]가 D[i−1][c]와 다르면 i번째를 넣은 것으로 보고 c에서 wᵢ를 뺍니다. 무게는 정수로 반올림하며, 두 목록의 개수가 같아야 하고 용량은 100,000 이하여야 합니다.
원리
마지막 물건에 대한 선택은 두 가지뿐입니다. 넣지 않거나, 넣고 나머지를 줄어든 용량으로 푸는 것입니다. 전체 최적해는 둘 중 나은 쪽이고, 각각은 물건이 적고 용량이 작은 더 작은 문제에만 의존합니다. 표의 칸이 (n + 1) × (용량 + 1)개이므로 시간은 O(n · W)입니다. W는 입력 크기가 아니라 수의 크기이므로 이를 의사 다항 시간이라 부르며, 배낭 문제는 일반적으로 NP-난해 문제입니다.
예제 풀이
- 입력값: 무게 1, 3, 4, 5, 가치 1, 4, 5, 7, 용량 7입니다.
- 표의 마지막 줄은 용량 0~7에 대해 0, 1, 1, 4, 5, 7, 8, 9이므로 최대 가치는 9입니다.
- 거꾸로 따라가면 3번(무게 4, 가치 5)과 2번(무게 3, 가치 4)을 골라 무게 7, 가치 9이므로 2, 3입니다.
- 무게당 가치가 큰 순서로 고르는 탐욕법은 4번(7 ÷ 5 = 1.4)을 먼저 넣고 남은 2에 1번을 넣어 8에 그칩니다.
결과 해석
결과는 주어진 수에 대한 정확한 최댓값이며, 같은 값을 내는 조합이 여럿이면 그중 하나를 보여 줍니다. 용량을 조금씩 바꿔 보면 용량 1단위가 늘 때 가치가 얼마나 늘어나는지 알 수 있습니다. 이 예에서 용량을 8로 늘리면 2번과 4번을 넣어 11이 됩니다.
흔한 실수
- 소수 무게를 그대로 넣는 경우입니다. 반올림되므로 1.25 kg은 10 g 단위로 125처럼 바꿔 넣습니다.
- 물건을 쪼갤 수 있는 분할 배낭 문제와 혼동합니다. 그 경우에는 탐욕법이 최적입니다.
- 같은 물건을 여러 번 넣을 수 있는 문제에 쓰는 경우입니다.
자주 묻는 질문
무게당 가치로 정렬하면 안 되나요?
예제처럼 용량이 남아 최적이 되지 않을 수 있으며, 물건을 쪼갤 수 있을 때만 최적입니다.
배낭 문제는 NP-완전인가요?
결정 문제 형태는 1972년 카프가 NP-완전임을 보였지만, 용량이 적당하면 동적 계획법으로 빠르게 풉니다.
메모리는 얼마나 쓰나요?
약 (n + 1) × (용량 + 1)개의 수가 필요하며, 최댓값만 구한다면 한 줄로도 충분합니다.
출처: R. M. Karp, "Reducibility among combinatorial problems", Complexity of Computer Computations, Plenum Press, 1972 · T. H. Cormen 외, Introduction to Algorithms, MIT Press