구현

이 장에서는 0/1 배낭 문제를 Python으로 구현합니다. 먼저 고른 물건까지 복원하는 전체 표 버전을, 이어서 한 행만 쓰는 버전을 만듭니다. 그다음 실제 부분 수열을 돌려주는 LCS 함수를 작성하고, 마지막으로 한 행 배낭 루틴을 C++, Java, TypeScript로 옮깁니다.

0/1 배낭 문제

물건이 n개 있고 각 물건에는 무게와 가치가 있습니다. 가방에는 최대 capacity만큼의 무게를 담을 수 있습니다. 각 물건은 한 번 담거나 담지 않거나 둘 중 하나("0/1")이며, 담은 물건의 가치 합을 최대로 만들어야 합니다.

• 상태: best[i][c] = 앞의 i개 물건만 써서 용량 c 안에 담을 수 있는 최대 가치
• 점화식: 물건 i를 건너뛰거나(best[i-1][c]), 들어간다면 담습니다(best[i-1][c - w] + v). 둘 중 큰 값을 고릅니다.
• 기저 사례: best[0][c] = 0. 물건이 없으면 가치도 없습니다.

Python: 복원까지 하는 전체 표

def knapsack(weights: list[int], values: list[int], capacity: int) -> tuple[int, list[int]]:
    n = len(weights)
    best = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(capacity + 1):
            best[i][c] = best[i - 1][c]
            if w <= c and best[i - 1][c - w] + v > best[i][c]:
                best[i][c] = best[i - 1][c - w] + v
    chosen, c = [], capacity
    for i in range(n, 0, -1):
        if best[i][c] != best[i - 1][c]:
            chosen.append(i - 1)
            c -= weights[i - 1]
    return best[n][capacity], chosen[::-1]


print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7))  # (9, [1, 2])

한 줄씩 살펴보면 다음과 같습니다.

• best는 n + 1행, capacity + 1열입니다. 0행은 모두 0으로 남아 기저 사례 역할을 합니다.
• Python 리스트는 0부터 세므로 i행은 i - 1번 물건을 뜻합니다. 그래서 w, v를 i - 1로 읽습니다.
• best[i][c] = best[i - 1][c]는 언제나 가능한 "건너뛰기" 선택입니다.
• if는 "담기" 선택을 시도합니다. 물건이 들어갈 때만, 그리고 더 좋을 때만 값을 바꿉니다.
• 표가 다 차면 best[n][capacity]가 최적 가치입니다.
• 복원은 아래 행에서 위 행으로 올라갑니다. 현재 용량에서 i - 1행과 i행의 값이 다르면 i - 1번 물건을 담았다는 뜻이므로 기록하고 그 무게만큼 용량을 줄입니다.

무게 [1, 3, 4, 5], 가치 [1, 4, 5, 7], 용량 7이면 1번과 2번 물건(무게 3 + 4, 가치 4 + 5 = 9)이 최선입니다. 0번과 3번을 담으면 8에 그칩니다.

Python: 한 행이면 충분하다

i행은 i - 1행만 읽으므로, 순서만 조심하면 리스트 하나로 두 행을 대신할 수 있습니다. 용량을 큰 쪽에서 작은 쪽으로 돌면 best[c - w]를 읽는 시점에 그 칸에는 아직 이전 행의 값이 남아 있습니다. 이것이 각 물건을 한 번만 쓰게 만드는 핵심입니다.

def knapsack_value(weights: list[int], values: list[int], capacity: int) -> int:
    best = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):  # 큰 용량부터: 물건마다 한 번만
            best[c] = max(best[c], best[c - w] + v)
    return best[capacity]


print(knapsack_value([1, 3, 4, 5], [1, 4, 5, 7], 7))  # 9

반대로 작은 용량부터 돌면 같은 행 안에서 물건을 다시 쓸 수 있게 되어, 물건마다 개수 제한이 없는 무한 배낭(unbounded knapsack)을 풀게 됩니다. 두 문제의 차이는 반복문 하나의 방향뿐입니다.

Python: 부분 수열까지 돌려주는 LCS

def lcs(a: str, b: str) -> str:
    n, m = len(a), len(b)
    L = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        for j in range(m - 1, -1, -1):
            if a[i] == b[j]:
                L[i][j] = L[i + 1][j + 1] + 1
            else:
                L[i][j] = max(L[i + 1][j], L[i][j + 1])
    out, i, j = [], 0, 0
    while i < n and j < m:
        if a[i] == b[j]:
            out.append(a[i])
            i, j = i + 1, j + 1
        elif L[i + 1][j] >= L[i][j + 1]:
            i += 1
        else:
            j += 1
    return "".join(out)


print(lcs("ABCBDAB", "BDCABA"))  # BDAB

이 버전은 L[i][j]를 접미사 a[i:]와 b[j:]에 대해 정의하고 표를 뒤에서부터 채웁니다. 덕분에 복원할 때 (0, 0)에서 앞으로 걸어가며 문자를 원래 순서대로 붙일 수 있고, 마지막에 뒤집을 필요가 없습니다.

C++

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

long long knapsack(const std::vector<int>& weights, const std::vector<long long>& values, int capacity) {
    std::vector<long long> best(capacity + 1, 0);
    for (size_t i = 0; i < weights.size(); ++i) {
        for (int c = capacity; c >= weights[i]; --c) {
            best[c] = std::max(best[c], best[c - weights[i]] + values[i]);
        }
    }
    return best[capacity];
}

int main() {
    std::cout << knapsack({1, 3, 4, 5}, {1, 4, 5, 7}, 7) << '\n';  // 9
}

가치를 많이 더하면 32비트 int를 넘을 수 있으므로 long long을 씁니다.

Java

public final class Knapsack {
    static long knapsack(int[] weights, long[] values, int capacity) {
        long[] best = new long[capacity + 1];
        for (int i = 0; i < weights.length; i++) {
            for (int c = capacity; c >= weights[i]; c--) {
                best[c] = Math.max(best[c], best[c - weights[i]] + values[i]);
            }
        }
        return best[capacity];
    }

    public static void main(String[] args) {
        System.out.println(knapsack(new int[] {1, 3, 4, 5}, new long[] {1, 4, 5, 7}, 7)); // 9
    }
}

TypeScript

function knapsack(weights: number[], values: number[], capacity: number): number {
  const best = new Array<number>(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let c = capacity; c >= weights[i]; c--) {
      best[c] = Math.max(best[c], best[c - weights[i]] + values[i]);
    }
  }
  return best[capacity];
}

console.log(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)); // 9

네 언어 모두 모양이 같습니다. 크기가 capacity + 1인 배열 하나, 물건에 대한 바깥 반복문, 큰 용량에서 작은 용량으로 내려가는 안쪽 반복문입니다.

정리

• 선택 내용을 복원해야 하면 전체 표를, 값만 필요하면 한 행을 씁니다.
• 한 행 0/1 배낭에서는 안쪽 반복문이 반드시 큰 용량에서 작은 용량으로 내려가야 합니다.
• LCS를 접미사로 정의하면 복원을 앞에서부터 할 수 있습니다.
• 핵심 루틴은 어느 언어에서나 몇 줄이며, C++과 Java에서는 정수 오버플로에 주의합니다.