Knapsack Problem

조합 최적화 문제 중 가장 유명한 문제 중 하나인 배낭 문제, 혹은 냅색 문제를 알아보자.

기본적인 문제 세팅은 다음과 같다.

최대 W 만큼의 무게를 담을 수 있는 배낭이 있다. 여기에 각각 가치와 무게가 다른 N개의 보석이 있다. 보석 i는 무게 w_i와 가치 v_i를 갖는다. 이때 가치의 합이 최대가 되도록 배낭에 보석을 담는 방법을 찾자.

보석을 쪼갤 수 있는 경우를 Fractional Knapsack 문제라고 하는데, 이 경우는 가치/무게가 높은 보석부터 골라서 넣는 탐욕법으로 쉽게 풀린다.

0-1 Knapsack

우리가 관심있는 다이나믹 프로그래밍의 단골 주제는 보석을 쪼갤 수 없는, 이른바 0-1 Knapsack 문제라고 한다. 이 문제를 수식으로 표현하면 다음 최적화 문제가 된다.

다음을 만족하는 \(x_1, x_2, ..., x_N\) 을 찾아야 한다:

\[\begin{equation} \begin{cases} \text{maximize: } & \sum_{i=1} ^{N} v_i x_i \\ \text{subject to:} & \sum{i=1} ^{N} w_i x_i \leq W \\ & x_i \in \{0, 1\}, 1 \leq i \leq N \\ \end{cases} \end{equation}\]

Naive Approach

가장 나이브한 접근은 모든 경우의 수를 다 나열해보면서 가치의 합이 최대가 되는 조합을 찾는 방법이다. 보석이 N개이고, 각각의 보석에 대해서 배낭에 넣거나(1) 빼거나(0) 둘 중 하나이므로 가능한 모든 경우의 수는 \(2^N\) 이 된다. 복잡도 \(O(2^N)\)은 터진다.

Dynamic Programming

다이나믹 프로그래밍이 동작하려면 두 가지 성질을 만족해야 한다.

첫 번째는 Optimal Substructure 이다. 최적 부분 구조… 라고도 말하는 것 같은데, 다음과 같이 정의한다.

부분 문제의 최적해로부터 전체 문제의 최적해를 만들 수 있을 때, 그 문제는 최적 부분 구조를 갖는다고 말한다. 즉, 어떤 문제의 최적해가 부분 문제의 최적해를 항상 포함한다.

두 번째는 Overlapping Subproblems, 부분 문제가 중복되어야 한다는 것이다. 다이나믹 프로그래밍은 결국 메모아이제이션, 캐싱이 핵심인데 이게 잘 동작하려면 당연히 같은 부분 문제를 여러 번 재활용할 수 있어야 한다.

이제 냅색 문제가 이 성질을 만족하는지 살펴보자. 어떤 해집합 A가 순서대로 k개의 보석을 가지고 만든 최적해라고 하자.

A가 k 번째 보석을 포함하지 않는다면, A는 나머지 k-1개의 보석들로 만든 최적해와 같을 것이다.
A가 k 번째 보석을 포함한다면, A는 k-1개의 보석들로 만든 최적해에 k 번째 보석을 추가한 것이다. 단, 이때 k 번째 보석을 넣을 수 있어야 한다.

그러므로 Optimal Substructure와 Overlapping Subproblems 두 성질을 모두 만족한다는 것을 알 수 있다. 이를 이용해서 첫 번째 보석부터 N 번째 보석까지 순서대로 해를 구해나가면 마지막에 구한 해집합이 곧 최적해가 된다.

이 내용을 수식으로 표현하면 다음과 같다. 먼저 여기서 정의된 문제를 \(\mathsf{Knapsack}(1, N, W)\) 라고 하자. 즉, 배낭의 무게 한도 W 내에서 최대의 가치가 되도록 N 개의 보석 중에서 고르는 문제이다. 최적해는 i 번째 보석을 고르거나 고르지 않도록 하는 변수의 튜플 \((x_1, x_2, ..., x_N)\) 이고 \(x_i \in \{0, 1\}, 1 \leq i \leq n\) 이다. 그러면,

만약 \(x_N = 0\), 즉 N 번째 보석을 고르지 않는다면, trivial 하게 \((x_1, x_2, ..., x_{N-1})\) 만으로도 최적해가 되고 이는 곧 \(\mathsf{Knapsak}(1, N-1, M)\)의 최적해와 같다.
만약 \(x_N = 1\), 즉 N 번째 보석을 고른다면, \((x_1, x_2, ..., x_{N-1})\) 는 \(\mathsf{Knapsak}(1, N-1, M - w_N)\)의 최적해와 같다.

이전의 “k 번째 보석을 넣을 수 있어야 한다”는 조건을 어떻게 수식에 표현했는지 눈여겨 보자 (\(M - w_N\)).

Optimal Substructure에 근거해서, 이 최적해를 다음과 같이 쪼개서 표현할 수 있다. 먼저 \(\mathsf{Knapsak}(1, N-1, M - w_N)\)의 최적해 \((x_1, x_2, ..., x_N)\) 를 \(\mathsf{Opt}(N, M)\) 이라고 하자. 그러면 이는 다음과 같다.

\[\begin{equation} \begin{split} \mathsf{Opt}(N, M) & = \mathtt{max}(\text{Case 1의 가치}, \text{Case 2의 가치}) \\ & = \mathtt{max}(\mathsf{Opt}(N-1, M), \mathsf{Opt}(N-1, M-w_N) + v_N) \\ \end{split} \end{equation}\]

조합 찾기

근데 이렇게 다이나믹 프로그래밍으로 풀면, 최적해가 만드는 가치의 합만을 알 수 있다. 최적해를 만드는 보석의 조합, 즉 \((x_1, x_2, ..., x_N)\) 의 맵핑은 어떻게 알 수 있을까?

최적해가 만드는 가치의 합인 \(\mathsf{Opt}(i, k)\) 을 생각해보자. 그러면 앞의 두 성질(로 부터 끌어낸 점화식)에 의해서,

\(\mathsf{Opt}(i, k) \neq \mathsf{Opt}(i - 1, k)\) 이라면, i 번째 보석이 포함되었다는 뜻이다 (by Case 2). 따라서 i 번째 보석을 포함했다고 기록하고 다음 보석을 찾기 위해서 \(i \mapsto i - 1, k \mapsto k - w_i\) 로 다음 것을 계산한다.
\(\mathsf{Opt}(i, k) = \mathsf{Opt}(i - 1, k)\) 라면 이는 곧 i 번째 보삭이 포함되지 않았다는 뜻이다 (by Case 1). 따라서 i 번째 보석을 포함하지 않았다고 기록하고, 다음 보석을 찾기 위해서 \(i \mapsto i - 1\) 로 진행하면 된다.