배낭 문제¶

소개¶

다음 예제를 살펴봅시다.

[USACO07 Dec] Charm Bracelet ¶

서로 다른 물건 $n$개와 용량이 $W$인 배낭이 있습니다. 각 물건에는 무게($w_{i}$)와 가치($v_{i}$)라는 2가지 속성이 있습니다. 총 무게가 용량 $W$를 넘지 않으면서 총 가치가 최대가 되도록 배낭에 넣을 물건의 부분집합을 골라야 합니다.

위 예제에서 각 물건이 가질 수 있는 상태는 두 가지(넣음 또는 넣지 않음)뿐이며, 이는 이진수 0과 1에 대응합니다. 따라서 이러한 유형의 문제를 "0-1 배낭 문제"라고 부릅니다.

0-1 배낭¶

설명¶

위 예제에서 문제의 입력은 다음과 같습니다. $i^{th}$ 물건의 무게 $w_{i}$, $i^{th}$ 물건의 가치 $v_{i}$, 그리고 배낭의 총 용량 $W$입니다.

앞의 $i$개 물건만 고려할 때 용량이 $j$인 배낭에 담을 수 있는 최대 총 가치를 저장하는 동적 계획법 상태를 $f_{i, j}$라고 합시다.

앞의 $i-1$개 물건에 대한 모든 상태가 이미 처리되었다고 가정하면, $i^{th}$ 물건에 대해서는 어떤 선택지가 있습니까?

배낭에 넣지 않는 경우, 남은 용량은 그대로이고 총 가치도 변하지 않습니다. 따라서 이 경우의 최댓값은 $f_{i-1, j}$입니다.
배낭에 넣는 경우, 남은 용량은 $w_{i}$만큼 줄어들고 총 가치는 $v_{i}$만큼 늘어나므로, 이 경우의 최댓값은 $f_{i-1, j-w_i} + v_i$입니다.

이로부터 dp 전이 방정식을 유도할 수 있습니다:

$$f_{i, j} = \max(f_{i-1, j}, f_{i-1, j-w_i} + v_i)$$

또한 $f_{i}$는 $f_{i-1}$에만 의존하므로 첫 번째 차원을 제거할 수 있습니다. 그러면 다음 전이 규칙을 얻습니다.

$$f_j \gets \max(f_j, f_{j-w_i}+v_i)$$

이 규칙은 $j$의 내림차순으로 실행해야 합니다(그래야 $f_{j-w_i}$가 $f_{i,j-w_i}$가 아니라 $f_{i-1,j-w_i}$에 암묵적으로 대응합니다).

배낭 문제의 전이 대부분이 이와 비슷한 방식으로 유도되므로, 이 전이 규칙을 이해하는 것이 중요합니다.

구현¶

앞서 설명한 알고리즘은 다음과 같이 $O(nW)$에 구현할 수 있습니다.

for (int i = 1; i <= n; i++)
  for (int j = W; j >= w[i]; j--)
    f[j] = max(f[j], f[j - w[i]] + v[i]);

다시 한번 실행 순서에 유의하십시오. 다음 불변식을 보장하려면 이 순서를 엄격히 지켜야 합니다. 쌍 $(i, j)$를 처리하기 직전에, $k > j$이면 $f_k$는 $f_{i,k}$에 대응하고, $k < j$이면 $f_{i-1,k}$에 대응합니다. 이로써 $f_{j-w_i}$가 $i$번째 단계가 아니라 $(i-1)$번째 단계에서 가져온 값임이 보장됩니다.

완전 배낭¶

완전 배낭 모델은 0-1 배낭과 비슷하며, 0-1 배낭과 유일하게 다른 점은 물건을 한 번만이 아니라 횟수 제한 없이 선택할 수 있다는 것입니다.

0-1 배낭의 아이디어를 참고하여 상태를 정의할 수 있습니다. $f_{i, j}$는 최대 용량이 $j$일 때 앞의 $i$개 물건을 사용하여 배낭이 얻을 수 있는 최대 가치입니다.

상태 정의는 0-1 배낭과 비슷하지만, 전이 규칙은 0-1 배낭과 다르다는 점에 유의해야 합니다.

설명¶

가장 단순한 접근은 처음 $i$개의 물건에 대해 각 물건을 몇 번 담을지를 모두 열거하는 것입니다. 이로부터 다음과 같은 전이 방정식을 얻습니다:

$$f_{i, j} = \max\limits_{k=0}^{\left\lfloor \frac{j}{w_i} \right\rfloor}(f_{i-1, j-k\cdot w_i} + k\cdot v_i)$$

앞에서 설명한 알고리즘은 다음과 같이 $O(nW^2)$에 구현할 수 있습니다.

for (int i = 1; i <= n; i++)
  for (int j = 0; j <= W; j++)
    for (int k = 0; k * w[i] <= j; k++)
      f[i][j] = max(f[i][j], f[i-1][j - k * w[i]] + k * v[i]);

동시에, 이는 "평평한" 방정식으로 단순화됩니다:

$$f_{i, j} = \max(f_{i-1, j},f_{i, j-w_i} + v_i)$$

이것이 성립하는 이유는 $f_{i, j-w_i}$가 이미 $f_{i, j-2\cdot w_i}$ 등에 의해 차례로 갱신되어 있기 때문입니다.

0-1 배낭 문제와 마찬가지로 첫 번째 차원을 제거하여 공간 복잡도를 최적화할 수 있습니다. 그러면 0-1 배낭 문제와 같은 전이 규칙을 얻습니다.

$$f_j \gets \max(f_j, f_{j-w_i}+v_i)$$

규칙은 동일하지만 이제는 $j$의 증가하는 순서로 실행해야 하며, 이 형태에서 두 문제의 차이는 이것뿐입니다. 위로 올라가며 진행하면 $f_{j-w_i}$는 이미 물건 $i$에 대해 갱신되어 있으므로 $f_{i,j-w_i}$에 해당하고, 따라서 그 물건을 다시 담을 수 있습니다. 반면 아래로 내려가며 진행하면 여전히 $f_{i-1,j-w_i}$에 해당하므로 각 물건은 최대 한 번만 담을 수 있습니다.

구현¶

앞에서 설명한 알고리즘은 다음과 같이 $O(nW)$에 구현할 수 있습니다.

for (int i = 1; i <= n; i++)
  for (int j = w[i]; j <= W; j++)
    f[j] = max(f[j], f[j - w[i]] + v[i]);

전이 규칙이 같음에도 불구하고 위의 코드는 0-1 배낭 문제에 대해서는 올바르지 않습니다.

코드를 주의 깊게 살펴보면, 현재 처리 중인 물건 $i$와 현재 상태 $f_{i,j}$에 대해 $j\geqslant w_{i}$일 때 $f_{i,j}$가 $f_{i,j-w_{i}}$의 영향을 받는다는 것을 알 수 있습니다. 이는 물건 $i$를 배낭에 여러 번 넣을 수 있는 것과 같으며, 0-1 배낭 문제가 아니라 완전 배낭 문제와 일치합니다.

다중 배낭 문제¶

다중 배낭 문제 역시 0-1 배낭 문제의 변형입니다. 주요한 차이점은 각 물건이 $1$개가 아니라 $k_i$개씩 있다는 것입니다.

설명¶

매우 간단한 아이디어는 "각 물건을 $k_i$번 선택하는 것"이 "같은 물건 $k_i$개를 하나씩 선택하는 것"과 같다는 것입니다. 따라서 이를 0-1 배낭 모델로 변환할 수 있으며, 이는 다음 전이 함수로 기술할 수 있습니다.

$$f_{i, j} = \max_{k=0}^{k_i}(f_{i-1,j-k\cdot w_i} + k\cdot v_i)$$

이 과정의 시간 복잡도는 $O(W\sum\limits_{i=1}^{n}k_i)$입니다.

이진 그룹화 최적화¶

여전히 최적화를 위해 다중 배낭 모델을 0-1 배낭 모델로 변환하는 방법을 고려합니다. 시간 복잡도 $O(Wn)$은 위의 접근으로는 더 이상 최적화할 수 없으므로, $O(\sum k_i)$ 부분에 집중합니다.

$i^{th}$ 물건에서 분리된 $j^{th}$ 물건을 $A_{i, j}$라고 합시다. 앞에서 논의한 단순한 접근에서는 모든 $j \leq k_i$에 대해 $A_{i, j}$가 같은 물건을 나타냅니다. 효율이 낮은 주된 이유는 반복적인 작업을 많이 하고 있기 때문입니다. 예를 들어 $\{A_{i, 1},A_{i, 2}\}$를 선택하는 경우와 $\{A_{i, 2}, A_{i, 3}\}$를 선택하는 경우를 생각해 봅시다. 이 두 경우는 완전히 동등합니다. 따라서 분리 방법을 최적화하면 시간 복잡도를 크게 줄일 수 있습니다.

이진 그룹화를 사용하면 그룹화를 더 효율적으로 할 수 있습니다.

구체적으로, $A_{i, j}$는 개별 물건 $2^j$개를 담습니다($j\in[0,\lfloor \log_2(k_i+1)\rfloor-1]$). $k_i + 1$이 $2$의 정수 거듭제곱이 아니라면, 크기가 $k_i-(2^{\lfloor \log_2(k_i+1)\rfloor}-1)$인 묶음을 하나 더 사용하여 나머지를 채웁니다.

위의 분할 방법을 사용하면 몇 개의 $A_{i, j}$를 선택하여 $\leq k_i$인 어떤 개수의 물건이든 만들 수 있습니다. 각 물건을 설명한 방식대로 분할한 후에는 0-1 배낭 방법으로 새롭게 정식화된 문제를 풀기만 하면 됩니다.

이 최적화를 통해 $O(W\sum\limits_{i=1}^{n}\log k_i)$의 시간 복잡도를 얻습니다.

구현¶

index = 0;
for (int i = 1; i <= n; i++) {
  int c = 1, p, h, k;
  cin >> p >> h >> k;
  while (k > c) {
    k -= c;
    list[++index].w = c * p;
    list[index].v = c * h;
    c *= 2;
  }
  list[++index].w = p * k;
  list[index].v = h * k;
}

단조 큐 최적화¶

이 최적화에서는 배낭 문제를 최대 큐 문제로 변환하는 것을 목표로 합니다.

설명의 편의를 위해 $g_{x, y} = f_{i, x \cdot w_i + y} ,\space g'_{x, y} = f_{i-1, x \cdot w_i + y}$라고 둡시다. 그러면 전이 규칙은 다음과 같이 쓸 수 있습니다:

$$g_{x, y} = \max_{k=0}^{k_i}(g'_{x-k, y} + v_i \cdot k)$$

나아가 $G_{x, y} = g'_{x, y} - v_i \cdot x$라고 둡시다. 그러면 전이 규칙은 다음과 같이 표현할 수 있습니다:

$$g_{x, y} \gets \max_{k=0}^{k_i}(G_{x-k, y}) + v_i \cdot x$$

이는 전형적인 단조 큐 최적화 형태가 됩니다. $G_{x, y}$는 $O(1)$에 계산할 수 있으므로, 고정된 $y$에 대해 $g_{x, y}$를 $O(\lfloor \frac{W}{w_i} \rfloor)$ 시간에 계산할 수 있습니다. 따라서 모든 $g_{x, y}$를 구하는 복잡도는 $O(\lfloor \frac{W}{w_i} \rfloor) \times O(w_i) = O(W)$입니다. 이렇게 하여 알고리즘의 전체 복잡도는 $O(nW)$로 줄어듭니다.

혼합 배낭¶

혼합 배낭 문제는 위에서 설명한 세 가지 문제가 결합된 것입니다. 즉, 어떤 물건은 한 번만 가져갈 수 있고, 어떤 물건은 무한히 가져갈 수 있으며, 어떤 물건은 최대 $k$번까지 가져갈 수 있습니다.

이 문제는 어려워 보일 수 있지만, 앞선 배낭 문제들의 핵심 아이디어를 이해하고 이를 결합하기만 하면 풀 수 있습니다. 풀이의 의사 코드는 다음과 같습니다:

for (each item) {
  if (0-1 knapsack)
    Apply 0-1 knapsack code;
  else if (complete knapsack)
    Apply the complete knapsack code;
  else if (multiple knapsack)
    Apply multiple knapsack code;
}