배낭 문제 (Knapsack)

정의

배낭 문제 (Knapsack Problem) 은 무게 제한 W 인 배낭에 가치 v_i, 무게 w_i 인 물건 N 개 중 일부를 담아 총 가치 최대화하는 조합 최적화 문제. NP-complete (decision version). DP 로 O(N × W) 의사 다항 시간 (pseudo-polynomial) 에 해결.

변형: 0-1 knapsack (각 물건 0개 또는 1개), unbounded knapsack (무한 개), fractional knapsack (분할 가능, 그리디로 O(N log N)).

문제 상황과 동기

N 개 물건, 배낭 용량 W.

• naive (완전 탐색): 2^N 부분 집합 → 각각 무게 합 ≤ W 확인. O(2^N), N=30 이면 10^9, 불가.
• 0-1 knapsack DP: O(N × W). W=10^4, N=100 이면 10^6, 가능.
• unbounded knapsack DP: O(N × W).
• fractional knapsack (그리디): 물건을 쪼갤 수 있으면 가치/무게 비율 정렬 후 탐욕. O(N log N).

핵심 통찰: “i 번째 물건까지, 무게 w 일 때 최대 가치” 를 상태로 하면 점화식 유도 가능.

PS: 자원 할당 (예산 제약 하 프로젝트 선택), 광고 슬롯 최적화, 암호화폐 포트폴리오.

시각화

핵심 아이디어

0-1 Knapsack

dp[i][w] = i 번째 물건까지 고려, 무게 w 일 때 최대 가치.

dp[0][w] = 0  (물건 0개, 가치 0)
dp[i][w] = max(
  dp[i-1][w],                   // i 번째 물건 안 담음
  dp[i-1][w - w_i] + v_i        // i 번째 물건 담음 (w ≥ w_i 일 때)
)

답: dp[N][W].

Unbounded Knapsack

각 물건을 무한 번 담을 수 있음. dp[i][w] 에서 i 번째 물건을 여러 번 담을 수 있으므로:

dp[i][w] = max(
  dp[i-1][w],                   // i 번째 물건 0개
  dp[i][w - w_i] + v_i          // i 번째 물건 1개 이상 (재귀적)
)

또는 1D 로 단순화:

dp[0] = 0
for i in 1..N:
    for w in w_i..W:
        dp[w] = max(dp[w], dp[w - w_i] + v_i)

Fractional Knapsack (그리디)

물건을 쪼갤 수 있으면 가치/무게 비율 정렬 후 큰 것부터 담음. O(N log N), DP 불필요.

1. 각 물건의 r_i = v_i / w_i 계산
2. r_i 내림차순 정렬
3. 순서대로 배낭이 꽉 찬 때까지 담음 (마지막 물건은 일부만)

알고리즘

0-1 Knapsack (2D DP)

knapsack_01(N, W, w[], v[]):
    dp[0..N][0..W] = 0
    for i in 1..N:
        for ww in 0..W:
            dp[i][ww] = dp[i-1][ww]
            if ww >= w[i]:
                dp[i][ww] = max(dp[i][ww], dp[i-1][ww - w[i]] + v[i])
    return dp[N][W]

공간 최적화 (1D DP)

dp[i][w] 가 dp[i-1][...] 만 참조 → rolling array.

knapsack_01_1D(N, W, w[], v[]):
    dp[0..W] = 0
    for i in 1..N:
        for ww in W down to w[i]:  // 역순
            dp[ww] = max(dp[ww], dp[ww - w[i]] + v[i])
    return dp[W]

역순 이유: dp[ww - w[i]] 가 이전 행 값이어야 하는데, 정순이면 이미 갱신됨.

구현

// 0-1 Knapsack, O(N × W) 시간, O(W) 공간
#include <bits/stdc++.h>
using namespace std;
​
int main() {
  int n, W; cin >> n >> W;
  vector<int> w(n + 1), v(n + 1);
  for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
​
  vector<int> dp(W + 1, 0);
  for (int i = 1; i <= n; i++) {
      for (int ww = W; ww >= w[i]; ww--)
          dp[ww] = max(dp[ww], dp[ww - w[i]] + v[i]);
  }
  cout << dp[W];
}

# 0-1 Knapsack, O(N × W) 시간, O(N × W) 공간
n, W = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(n)]
​
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
  w_i, v_i = items[i - 1]
  for ww in range(W + 1):
      dp[i][ww] = dp[i-1][ww]
      if ww >= w_i:
          dp[i][ww] = max(dp[i][ww], dp[i-1][ww - w_i] + v_i)
print(dp[n][W])

// Unbounded Knapsack, O(N × W) 시간, O(W) 공간
import java.util.*;
​
public class Main {
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt(), W = sc.nextInt();
      int[] w = new int[n + 1], v = new int[n + 1];
      for (int i = 1; i <= n; i++) {
          w[i] = sc.nextInt(); v[i] = sc.nextInt();
      }
​
      int[] dp = new int[W + 1];
      for (int i = 1; i <= n; i++) {
          for (int ww = w[i]; ww <= W; ww++)  // 정순 (unbounded)
              dp[ww] = Math.max(dp[ww], dp[ww - w[i]] + v[i]);
      }
      System.out.println(dp[W]);
  }
}

4 7
6 13
4 8
3 6
5 12

14

복잡도

의사 다항 시간 (pseudo-polynomial): W 가 입력 크기 log W 에 비례하지 않음. W=10^9 면 불가 → W ≤ 10^4~10^5 로 제한된 문제만 DP.

변형 / 활용

1. 배낭에 담은 물건 추적

dp[i][w] 갱신 시 선택 기록:

vector<vector<bool>> take(n + 1, vector<bool>(W + 1));
for (int i = 1; i <= n; i++) {
    for (int ww = W; ww >= w[i]; ww--) {
        if (dp[ww - w[i]] + v[i] > dp[ww]) {
            dp[ww] = dp[ww - w[i]] + v[i];
            take[i][ww] = true;
        }
    }
}
// backtrack
int ww = W;
for (int i = n; i >= 1; i--) {
    if (take[i][ww]) {
        cout << "물건 " << i << " 담음\n";
        ww -= w[i];
    }
}

2. 정확히 무게 W 채우기

초기값을 dp[0] = 0, dp[1..W] = -∞ 로. 도달 불가한 무게는 -∞ 유지.

3. 다중 배낭 (Multiple Knapsack)

각 물건 i 를 최대 c_i 개 담을 수 있음. 이진 분해 (binary decomposition): c_i 를 1, 2, 4, …, 2^k, remainder 로 쪼개 0-1 knapsack 으로 변환 → O(N × W × log C).

4. 2D Knapsack

무게 W, 부피 V 두 제약. dp[i][w][v] = i 번째 물건까지, 무게 w, 부피 v 일 때 최대 가치. O(N × W × V).

함정

1. 1D DP 에서 정순 / 역순

0-1 knapsack 은 역순 (ww = W down to w[i]). unbounded 는 정순 (ww = w[i] to W). 헷갈리면 틀림.

2. 초기값

dp[0] = 0, 나머지는 0 (최대화) 또는 -∞ (정확히 W 채우기) 또는 ∞ (최소화).

3. W 가 너무 큼

W=10^9 이면 O(N × W) 불가. W 대신 v (가치) 기준 DP (dp[i][v] = 가치 v 를 만드는 최소 무게) 로 전환 → O(N × V_total).

4. 오버플로우

v_i 가 크면 dp[w] 합이 int 범위 초과. long long 사용.

5. 물건 인덱스 1-indexed

코드에서 w[i], v[i] 가 0-indexed 인지 1-indexed 인지 일관성.

BOJ 연습 문제

참고

• 동적 계획법
• 그리디 알고리즘 (fractional knapsack)
• 중간에서 만나기 (N=40, W 큰 경우)