[PAST] Part 2 보충 — 배낭 문제 풀이

이 글을 쓰는 이유

본편에서 배낭 문제는 "복습"이라는 이름으로 지나갔습니다. 정의를 세우고, 점화식을 두 갈래로 나누고, Java 구현 두 개를 붙이는 데까지가 전부였습니다. 그런데 배낭 문제에서 실제로 시간을 잡아먹는 것은 그 뼈대가 아니라 뼈대에 붙어 있는 자잘한 판단들입니다.

• 왜 답을 dp[N][W] 한 칸에서 읽지 않고 마지막 행 전체를 훑는가?
• 1차원으로 접을 때 "역순으로 돌아라"는 말은 알겠는데, 정순으로 돌리면 구체적으로 어느 칸이 어떻게 망가지는가?
• 최댓값 말고 어떤 품목을 골랐는지는 어떻게 알아내는가?
• 제약이 바뀌면 이 풀이는 어디서부터 무너지는가?

이 글은 그 네 가지에 답합니다. 본편과 겹치는 부분은 2절에서 다섯 줄로 압축하고 넘어가겠습니다.

1. 문제를 다시 읽는다 — 제약이 설계를 결정한다

$N$개의 품목이 있고 품목 $i$의 무게는 $w_i$, 가치는 $v_i$입니다. 무게의 총합이 $W$ 이하가 되도록 몇 개를 골라, 가치의 총합의 최댓값을 구합니다.

여기까지는 누구나 읽습니다. 중요한 것은 그 아래 붙어 있는 제약 네 줄입니다. 경험이 쌓이면 이 네 줄만 보고도 구현의 골격이 거의 정해집니다.

2. 본편 요약 — 여기까지는 이미 한 이야기

본편에서 세운 정의와 점화식만 옮겨 둡니다. 자세한 유도 과정은 본편 2.1절을 봐 주세요.

dp[i][j] ← 번호가 작은 i개의 품목(품목 0, 1, ..., i-1)만 고려하여,
           무게의 총합이 정확히 j가 되도록 몇 개 골랐을 때 가치의 총합의 최댓값
           (무게의 총합을 j로 만들 수 없는 경우는 -∞)

• 초기 조건 — dp[0][0] = 0, 나머지는 $-\infty$
• 품목 $i$를 고르지 않는다 — $dp[i+1][j] = dp[i][j]$
• 품목 $i$를 고른다 — $dp[i+1][j] = dp[i][j - w_i] + v_i$ (단 $j \geq w_i$)
• 답 — 마지막 행 전체의 최댓값 $\max_j dp[N][j]$
• 계산량 — $O(NW)$

이 정의를 정의 A라고 부르겠습니다. 4절에서 다른 정의와 비교할 것이기 때문입니다.

3. 손으로 표를 채워 본다

점화식을 읽어서 이해한 기분이 드는 것과, 표가 실제로 어떻게 채워지는지 아는 것은 다릅니다. 서적과 AtCoder가 함께 제시하는 예제 입력을 그대로 쓰겠습니다.

3 8        ← N = 3, W = 8
3 30       ← 품목 0: 무게 3, 가치 30
4 50       ← 품목 1: 무게 4, 가치 50
5 60       ← 품목 2: 무게 5, 가치 60

정답은 90입니다. 품목 0과 2를 고르면 무게 $3 + 5 = 8$, 가치 $30 + 60 = 90$이 됩니다.

이제 정의 A의 표를 한 행씩 채웁니다. $i$번째 행은 "품목 $i-1$까지 처리한 직후"의 상태입니다. $i=0$행이 "아무것도 보지 않은 상태"라는 점에 주의하세요.

몇 칸만 소리 내어 읽어 봅시다

• $dp[1][3] = 30$ — 품목 0(무게 3)만으로 무게 3을 만드는 유일한 방법입니다. $dp[0][3 - 3] + 30 = dp[0][0] + 30 = 30$.
• $dp[2][7] = 80$ — 품목 1을 쓰는 갈래에서 $dp[1][7 - 4] + 50 = dp[1][3] + 50 = 30 + 50 = 80$. 즉 품목 0과 1을 둘 다 고른 상태입니다. 표의 한 칸이 조합 하나를 대표하고 있는 셈입니다.
• $dp[3][8] = 90$ — $dp[2][8 - 5] + 60 = dp[2][3] + 60 = 30 + 60 = 90$. 품목 0과 2의 조합이고, 이것이 답입니다.

4. 정의를 바꿔 본다 — "정확히 $j$" vs "$j$ 이하"

3절 끝의 불편함("답을 읽으려고 행 전체를 훑어야 한다")은 정의를 조금 바꾸면 사라집니다.

dp[i][j] ← 번호가 작은 i개의 품목만 고려하여,
           무게의 총합이 j 이하가 되도록 골랐을 때 가치의 총합의 최댓값

이것을 정의 B라 부릅시다. 점화식은 정의 A와 글자 하나 다르지 않습니다. 바뀌는 것은 앞뒤 두 군데뿐입니다.

같은 입력으로 정의 B의 표를 채우면 이렇게 됩니다.

두 표의 마지막 행을 나란히 놓으면 관계가 한눈에 보입니다.

정의 A:  0  -∞  -∞  30  50  60  -∞  80  90
정의 B:  0   0   0  30  50  60  60  80  90
                                 ↑
                    A 의 j=6 은 만들 수 없는 칸이지만,
                    B 의 j=6 은 "무게 5 로 얻은 60 을 그대로 들고 있다"

즉 정의 B의 마지막 행은 정의 A 마지막 행의 누적 최댓값(prefix max)입니다. 정의 B는 "행 전체를 훑는" 작업을 표를 채우는 과정 안으로 흡수해 버린 것입니다.

5. 1차원으로 접기 — 정순으로 돌리면 무슨 일이 벌어지는가

본편에서 2차원 배열이 $101 \times 100001$개의 long, 약 80MB를 차지한다고 했습니다. dp[i+1]이 dp[i]만을 참조하므로 1차원으로 접을 수 있고, 그때 $j$를 큰 쪽부터 돌아야 한다고 했습니다.

long[] dp = new long[W + 1];
Arrays.fill(dp, NEG);
dp[0] = 0;

for (int i = 0; i < N; i++) {
    // j 를 역순으로 — 같은 품목을 두 번 담는 것을 막는다
    for (int j = W; j >= w[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
    }
}

"같은 품목을 두 번 담게 된다"는 설명은 맞지만, 추상적입니다. 실제로 어느 칸이 언제 망가지는지 같은 입력으로 확인해 봅시다.

역순으로 돌린 경우 (정답)

3절의 2차원 표에서 $i=1, 2, 3$행을 그대로 떼어 온 것과 완전히 같습니다. 접기가 성공한 것입니다.

정순으로 돌린 경우 (반례)

루프를 for (int j = w[i]; j <= W; j++)로 바꾸기만 하면 이렇게 됩니다.

답이 100으로 나옵니다. 정답 90보다 큽니다.

망가지는 순간을 정확히 짚을 수 있습니다. 첫 행의 $j = 6$입니다. 품목 0 하나를 처리하는 동안, $j = 3$에서 dp[3] = 30으로 갱신한 뒤 루프가 계속 올라가 $j = 6$에 도달하면

$$dp[6] = dp[6 - 3] + 30 = dp[3] + 30 = 30 + 30 = 60$$

을 계산합니다. 이때 읽은 dp[3]은 방금 이 루프가 품목 0을 써서 만든 값입니다. 그러니 $dp[6] = 60$은 "품목 0을 두 번 담았다"는 뜻입니다. 역순으로 돌면 $j = 6$을 $j = 3$보다 먼저 처리하므로, dp[3]은 아직 "품목 0을 쓰기 전"의 값($-\infty$)이고 오염이 일어나지 않습니다.

그 뒤 $j = 8$의 100은 품목 1(무게 4, 가치 50)을 두 번 담은 값입니다. 확인해 보면 이 정순 코드가 내놓는 답은 무한 개수 배낭 문제(unbounded knapsack)의 정답과 정확히 일치합니다.

// 0-1 배낭 — 각 품목을 최대 1개
for (int j = W; j >= w[i]; j--) dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);

// 무한 개수 배낭 — 각 품목을 몇 개든
for (int j = w[i]; j <= W; j++) dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);

6. 어떤 품목을 골랐는가 — 복원

대회에서는 최댓값만 출력하면 끝이지만, 현실의 최적화 문제에서 "최댓값은 90입니다"만으로 끝나는 경우는 없습니다. 무엇을 골라야 90이 되는지를 답해야 합니다.

2차원 표를 남겨 두었다면 복원은 어렵지 않습니다. 마지막 행에서 답이 있는 칸을 찾아 거꾸로 거슬러 올라가면서, 각 단계에서 품목 $i$를 썼는지 판정하면 됩니다.

// dp 는 3절의 2차원 표 (정의 A)
private static List<Integer> restore(long[][] dp, int N, int W, int[] w) {
    // 답이 있는 칸부터 시작한다 — 마지막 행의 최댓값 위치
    int j = 0;
    for (int t = 0; t <= W; t++) {
        if (dp[N][t] > dp[N][j]) j = t;
    }

    List<Integer> chosen = new ArrayList<>();
    for (int i = N - 1; i >= 0; i--) {
        // dp[i+1][j] 가 dp[i][j] 와 다르다면, 그 값은 「품목 i 를 고르는」
        // 갈래에서 온 것이다 = 품목 i 를 썼다
        if (dp[i + 1][j] != dp[i][j]) {
            chosen.add(i);
            j -= w[i];      // 품목 i 의 무게만큼 되돌린다
        }
    }
    Collections.reverse(chosen);
    return chosen;          // [0, 2]
}

예제 입력으로 돌리면 [0, 2]가 나옵니다. 무게 $3 + 5 = 8$, 가치 $30 + 60 = 90$ — 서적이 설명한 최적해와 일치합니다.

7. 제약이 뒤집히면 — 첨자도 뒤집는다 (EDPC E)

지금까지의 풀이는 $O(NW)$였습니다. 이 계산량은 $W$가 작다는 데 전적으로 기대고 있습니다. 그러면 $W$가 커지면 어떻게 될까요?

문제문은 D와 한 글자도 다르지 않습니다. 다른 것은 제약뿐입니다.

$W$를 첨자로 쓸 수 없게 되었습니다. 그런데 제약을 다시 보면, $v_i$ 쪽이 작아졌습니다. 가치의 총합은 최대 $100 \times 10^3 = 10^5$입니다. 방금 $W$가 있던 자리에 딱 맞는 크기입니다.

여기서 이 시리즈의 핵심 감각이 나옵니다. 무엇을 첨자로 들고 갈지는 우리가 고르는 것이 아니라 제약이 정해 줍니다. 그러니 무게와 가치의 역할을 통째로 맞바꿉시다.

dp[i][x] ← 앞의 i개 품목만 고려하여,
           가치의 총합이 정확히 x가 되도록 골랐을 때 무게의 총합의 최솟값
           (가치의 총합을 x로 만들 수 없는 경우는 +∞)

"최댓값을 구하라"는 문제가 최솟값 DP로 바뀌었습니다. 답은 "무게가 $W$ 이하인 $x$ 중 가장 큰 것"입니다. 같은 예제 입력으로 채워 보면 이렇게 됩니다.

(표에 없는 $x$는 전부 $+\infty$ — 만들 수 없는 가치입니다.) ✓가 붙은 것 중 가장 오른쪽이 $x = 90$이고, 이것이 답입니다. D와 같은 90이 나왔습니다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        long W = Long.parseLong(st.nextToken());   // 10^9 까지 — int 도 되지만 long 이 안전하다

        int[] w = new int[N];
        int[] v = new int[N];
        int V = 0;                  // 가치의 총합 = 첨자의 상한
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            w[i] = Integer.parseInt(st.nextToken());
            v[i] = Integer.parseInt(st.nextToken());
            V += v[i];
        }

        // 무게의 총합은 최대 100 * 10^9 = 10^11 이므로 long
        final long INF = Long.MAX_VALUE / 4;

        // dp[x] = 가치의 총합이 정확히 x 일 때 무게의 최솟값
        long[] dp = new long[V + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;

        for (int i = 0; i < N; i++) {
            // 5절과 같은 이유로 역순 — 같은 품목을 두 번 쓰지 않기 위해
            for (int x = V; x >= v[i]; x--) {
                if (dp[x - v[i]] < INF) {
                    dp[x] = Math.min(dp[x], dp[x - v[i]] + w[i]);
                }
            }
        }

        // 무게가 W 이하인 것 중 가장 큰 가치
        int ans = 0;
        for (int x = 0; x <= V; x++) {
            if (dp[x] <= W) ans = x;
        }
        System.out.println(ans);
    }
}

계산량은 $O(N \sum v_i) = 100 \times 10^5 = 10^7$ — D와 똑같은 규모로 돌아왔습니다.

8. 자주 틀리는 지점 5선

9. 연습 문제

같은 사고방식이 통하는 문제들입니다. 위에서 아래로 갈수록 "첨자에 무엇을 들고 갈 것인가"를 스스로 정해야 하는 폭이 커집니다.

정리

• 제약을 먼저 곱해 보면 표의 크기와 자료형이 그 자리에서 정해집니다. $N \times W$는 시간, $N \times \max v_i$는 int/long을 결정합니다.
• "정확히 $j$"와 "$j$ 이하"는 점화식이 같고 초기화와 답 읽는 위치만 짝을 이뤄 바뀝니다. 후자의 마지막 행은 전자의 누적 최댓값입니다.
• 1차원 롤링의 루프 방향은 문제의 종류를 말해 줍니다. 역순이면 0-1 배낭, 정순이면 무한 개수 배낭입니다.
• 복원은 2차원 표가 남아 있을 때만 가능합니다. 메모리를 아끼면 "무엇을 골랐는가"를 잃습니다.
• 첨자에 무엇을 들고 갈지는 제약이 정합니다. $O(N \times \text{무언가})$가 터지면, 그 자리에 들어갈 더 작은 후보를 찾으세요.

참고 자료

• 본편: [PAST] Part 2 — 동적 계획법 심화 ①
• 서적: 「アルゴリズム実技検定 公式テキスト ［上級］～［エキスパート］編」 (マイナビ出版, 2023) — 제2장 2.1절, 예제 2-1-1
• 소스코드: tsutaj/pastbook-2-source-code (Github)
• Educational DP Contest: https://atcoder.jp/contests/dp
• AtCoder 공식 사이트: https://atcoder.jp