0x06. 배낭 문제 (Knapsack Problem)

배낭 문제란?

배낭 문제(Knapsack Problem)는 제한된 용량의 배낭에 가치가 서로 다른 물건들을 어떻게 담아야 최대 가치를 얻을 수 있는가를 묻는 최적화 문제다. 이사할 때 트렁크 용량이 한정되어 있는데, 짐마다 중요도가 다르다면 무엇부터 넣어야 할지 고민하는 상황과 같다.

배낭 문제는 크게 두 가지 버전으로 나뉜다.

1. 0-1 Knapsack Problem

물건을 통째로 넣거나 빼거나 둘 중 하나다. 쪼갤 수 없다.
Dynamic Programming(DP) 으로 풀어야 하며, Greedy로는 최적해를 보장할 수 없다.

2. Fractional Knapsack Problem

물건을 원하는 만큼 쪼개서 넣을 수 있다.
각 물건의 단위 무게당 가치(value per weight, $v_i / w_i$ ) 를 계산한 뒤, 가치가 높은 것부터 최대한 많이 담는 Greedy 전략으로 최적해를 구할 수 있다.

두 문제 모두 최적 부분 구조(Optimal Substructure) 를 가진다. 하지만 탐욕 선택 속성(Greedy Choice Property) 은 Fractional Knapsack에만 성립하기 때문에, 0-1 Knapsack에는 Greedy를 적용할 수 없다.

0-1 Knapsack Problem

0-1 Knapsack은 물건을 쪼갤 수 없으므로 각 물건에 대해 "넣는다 / 넣지 않는다"의 이진 선택만 가능하다. 이 문제를 해결하는 네 가지 접근법을 살펴본다.

Brute Force

가장 직관적인 방법은 모든 조합을 시도하는 것이다. n개의 물건이 있으면 각각을 넣거나 빼는 $2^n$ 가지 조합이 존재한다. 이 중에서 총 무게가 W 이하이면서 총 가치가 최대인 조합을 찾으면 된다.

당연히 시간 복잡도는 $\Theta(2^n)$ 으로, 물건의 수가 조금만 늘어나도 현실적으로 사용할 수 없다.

Greedy

Greedy 전략은 0-1 Knapsack에서는 최적해를 보장하지 못한다. 단위 가치가 높은 물건부터 담는다고 해서 반드시 전체 최적해가 되지는 않기 때문이다.

Dynamic Programming

0-1 Knapsack의 실질적인 해법은 DP(Dynamic Programming) 다. DP에서 가장 중요한 것은 부분 문제(Subproblem)를 올바르게 정의하는 것이다.

부분 문제 정의: 첫 번째 시도

물건에 1부터 n까지 번호를 매기고, $S_k$ = {물건 1, 2, ..., k}로 정의해 보자. 이는 가장 단순한 부분 문제 정의이긴 하지만, 최종 해 $S_n$ 을 부분 문제 $S_k$ 로 표현하려고 하면 문제가 생긴다.

위 그림에서 볼 수 있듯이, 물건 집합만으로는 부분 문제 간의 관계를 제대로 기술할 수 없다. 이 정의에는 결함(flaw) 이 있으므로 새로운 정의가 필요하다.

부분 문제 정의: 매개변수 추가

해결책은 무게(w) 라는 매개변수를 추가하는 것이다. 부분 문제를 B[k, w] 로 정의하면, "물건 1~k 중에서 총 무게가 w 이하가 되도록 골랐을 때의 최대 가치"를 나타낸다.

$S_k$ 의 최적 부분 집합이 총 무게 W를 가질 때, 물건 k를 포함하거나 포함하지 않거나 둘 중 하나다.

Case 1: $w_k$ > W 이면, 물건 k는 배낭에 들어갈 수 없다. 따라서 B[k, w] = B[k-1, w]가 된다.
Case 2: $w_k$ ≤ W 이면, 물건 k를 넣을 수도 있다. 넣는 경우와 넣지 않는 경우 중 더 큰 가치를 선택한다.

이를 의사 코드로 표현하면 다음과 같다.

for w = 0 to W
    B[0, w] = 0         // 물건이 0개면 가치도 0

for i = 1 to n
    B[i, 0] = 0         // 무게 한도가 0이면 아무것도 못 넣음
    for w = 1 to W
        if w[i] <= w     // 물건 i를 넣을 수 있는 경우
            if b[i] + B[i-1, w - w[i]] > B[i-1, w]
                B[i, w] = b[i] + B[i-1, w - w[i]]
            else
                B[i, w] = B[i-1, w]
        else
            B[i, w] = B[i-1, w]   // w[i] > w, 넣을 수 없음