[DP] Knapsack Problem (0-1 Knapsack)

References

• Algorithms (Sanjoy Dasgupta)

Contents

• Knapsack Problem (배낭 문제)
• with repetition
• without repetition

---

Knapsack Problem

배낭 문제(knapsack problem)는 간단하게 다음과 같습니다.

한 여행가의 배낭에 담을 수 있는 무게의 최댓값(W)이 정해져 있습니다. 담을 수 있는 항목은 총 n개가 있는데, 이들의 무게는 \(w_1, \cdots, w_n\)이고, 그 항목의 가치는 \(v_1, \cdots, v_n\) 일 때, 가치의 합이 최대가 되도록 배낭에 담을 항목을 고르는 방법은 무엇일까요?

 

예를 들어, W = 10일 때를 생각해보도록 하겠습니다.

이 문제는 두 종류의 버전이 존재합니다. 만약 각 항목의 수량에 제한이 없는 경우, 최적의 답은 1번 항목 하나와 4번 항목 2개를 고르는 것(총 $48) 입니다. 반면, 각 항목이 오직 하나만 존재하는 경우에는 1번 항목과 3번 항목을 고르는 것(총 $46) 입니다.

 

문제를 살펴보면 이 문제에 다항 시간에 해결되는 알고리즘은 없는 것 같습니다. 하지만 동적 프로그래밍을 사용하면 이 문제를 O(nW) 시간 내에 해결할 수 있습니다. 이 시간은 W가 작을 때는 합리적이지만, 입력의 크기가 W가 아닌 logW에 비례하기 때문에 다항식은 아닙니다.

 

여기서 배낭에 담을 수 있는 각 항목은 쪼개지지 않는데, 이렇게 가치가 무게 별로 나누어지지 않는 항목들에 대한 문제를 0-1 Knapsack 문제라고 합니다. 이번 포스팅에서는 0-1 배낭 문제에 대해 다룹니다.

---

Knapsack with repetition

반복을 허용하는, 즉, 각 항목의 수량에 제한이 없는 경우의 버전을 먼저 살펴보겠습니다.

당연하지만, 동적 프로그래밍의 주된 질문은 '하위 문제(subproblems)가 무엇인가?' 입니다. 이 경우에는 두 가지 방법들을 통해 원래의 문제를 축소시킬 수 있습니다.

즉, \(w \leq W\)인 더 작은 용량의 배낭을 조사하거나, \(j \leq n\)인 더 적은 항목들을 조사하는 것 입니다. 정확히 이 작업이 무엇인지 살펴보기 위해서 간단한 실험을 수행해보겠습니다.

 

첫 번째 제약은 더 작은 용량을 요구한다는 것입니다. 따라서, 다음과 같이 정의합니다.

K(w) = w 무게의 배낭을 가지고 얻을 수 있는 최대 가치

이 정의를 더 작은 하위 문제들로 표현할 수 있을까요? 

만약 K(w)에 대한 최적의 솔루션이 i번째 항목을 포함한다면, 이때 배낭으로부터 이 항목을 제거하는 것은 K(\(w - w_i\))에 대한 최적의 솔루션을 남깁니다. 다시 말하면, K(w)는 임의의 i에 대해 단순히 K(\(w - w_i\)) + \(v_i\) 입니다. 여기서 우리는 이 i에 대해 알지 못하기 때문에 모든 가능성에 대해 시도할 필요가 있습니다.

\[K(w) = \underset{i:w_i \leq w}{max}\{K(w-w_i) + v_i\}\]

위 정의에서 빈 집합에 대한 최댓값은 0입니다.

 

위 정의를 통해서 알고리즘은 이제 다음과 같이 간단하게 작성될 수 있습니다.

위 알고리즘은 길이가 W+1인 1차원 배열을 왼쪽에서 오른쪽의 순서로 채웁니다. 각 배열의 항목들을 O(n) 시간 내에 계산될 수 있으며, 따라서 전체 실행 시간은 O(nW)가 됩니다.

 

이전 포스팅에서 DP에 대해서 알아봤었는데, 언급한 것처럼 DAG를 구축하여 최장 경로를 찾음으로써 이 문제를 해결할 수 있습니다.

 

C++로 구현하면 다음과 같이 구현할 수 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>

int knapsack_with_repetition(const std::vector<int>& weights, const std::vector<int>& values, const int W)
{
    const int N = weights.size();

    std::vector<int> K(W + 1, 0);
    for (int w = 1; w <= W; w++) {
        for (int i = 0; i < N; i++) {
            if (weights[i] <= w) {
                K[w] = std::max(K[w - weights[i]] + values[i], K[w]);
            }
        }
    }

    return K[W];
}

int main(int argc, char* argv[])
{
    const int W = 10;
    std::vector<int> w{ 6, 3, 4, 2 };
    std::vector<int> v{ 30, 14, 16, 9 };

    std::cout << "Total values: " << knapsack_with_repetition(w, v, W) << "\n";
}

 

---

Knapsack without repetition

두 번째 버전은 바로 각 항목을 반복적으로 선택할 수 없는, 즉, 각 항목이 단 하나만 존재하는 경우입니다. 이렇게 되면 위에서 설명한 하위 문제들은 여기서는 사용할 수 없게 됩니다. 예를 들면, 우리가 n번째 항목이 하위 문제에서 이미 사용되었는지 모르기 때문에 K(\(w - w_n\))의 크기가 아주 크다는 것을 아는 것이 아무런 도움이 되지 않습니다. 따라서, 사용된 항목들에 대한 추가적인 정보를 전달하기 위해 하위 문제를 재정의해야 합니다. 여기서는 j라는 두 번째 파라미터를 정의하며, 이는 \(0 \leq j \leq n\)을 만족합니다.

K(w, j) = w 무게를 담을 수 있는 배낭과 \(1, \cdots, j\) 항목을 사용하여 얻을 수 있는 최대 가치

이렇게 정의했을 때, 우리가 찾는 정답은 K(W, n)이 됩니다.

 

하위 문제들에 대한 K(w, j)를 어떻게 표현할 수 있을까요? 

이는 아주 단순한데, 항목 j가 최적의 솔루션을 얻는데 필요한지, 아닌지만을 결정하면 됩니다.

\[K(w, j) = max\{K(w - w_j, j-1) + v_j, K(w, j-1)\}\]

(여기서 첫 번째 케이스의 경우에는 오직 \(w_j \leq w\)일 때만 발생합니다.)

 

정리하면, 하위 문제 K(., j-1)에 대해 K(w, j)로 표현할 수 있습니다.

이때 알고리즘은 W+1개의 행과 n+1개의 열을 갖는 2차원 테이블(배열)을 채움으로써 수행됩니다. 각 배열의 항목들은 정확히 상수 시간이 걸립니다. 따라서 비록 테이블(배열)이 반복이 허용된 버전보다 크지만, 동일하게 O(nW)의 시간이 걸립니다.

알고리즘은 다음과 같습니다.

 

위 알고리즘의 C++ 구현은 다음과 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>

int knapsack_without_repetition(const std::vector<int>& weights, const std::vector<int>& values, const int W)
{
    const int N = weights.size();

    std::vector<std::vector<int>> K(W + 1, std::vector<int>(N+1, 0));
    
    for (int j = 1; j <= N; j++) {
        for (int w = 1; w <= W; w++) {
            if (weights[j - 1] <= w) {
                K[w][j] = std::max(K[w][j - 1], K[w - weights[j - 1]][j - 1] + values[j - 1]);
            }
            else {
                K[w][j] = K[w][j - 1];
            }
        }
    }

    return K[W][N];
}

int main(int argc, char* argv[])
{
    const int W = 10;
    std::vector<int> w{ 6, 3, 4, 2 };
    std::vector<int> v{ 30, 14, 16, 9 };

    std::cout << "Total values: " << knapsack_without_repetition(w, v, W) << "\n";
}