배낭 문제

어떤 문제를 푸는가

용량이 \(W\)인 가방에, 무게 \(w_i\)와 가치 \(v_i\)를 가진 물건들을 넣어 가치 합을
최대화 합니다. 각 물건은 넣거나 안 넣거나 둘 중 하나(0/1 배낭). 그리디로
"가치/무게 비율이 높은 것부터"는 0/1에서는 틀립니다. 반례가 쉽게 나옵니다.

상태 정의

DP의 출발은 항상 "상태가 무엇을 뜻하는가"입니다.

$$ dp[i][c] = \text{앞에서 } i \text{개의 물건만 고려하고, 용량이 } c \text{일 때 최대 가치} $$

점화식

\(i\)번째 물건을 볼 때 선택지는 둘입니다.

• 안 넣는다 — dp[i-1][c] 그대로.
• 넣는다 (단, \(c \ge w_i\)일 때) — dp[i-1][c - w_i] + v_i.

$$ dp[i][c] = \max\bigl(dp[i-1][c],\ dp[i-1][c - w_i] + v_i\bigr) $$

기저는 dp[0][c] = 0 (물건이 없으면 가치 0). 답은 dp[N][W] 입니다.

왜 옳은가

각 물건에 대한 결정은 이전 물건들의 최적해와 독립적 입니다. "i-1개까지의
최적 가치"를 알고 있으면, i번째를 넣을지 말지만 비교하면 됩니다. 부분 문제의
최적해가 전체의 최적해를 이룬다는 최적 부분 구조가 성립하므로 DP가
유효합니다. 또한 같은 (i, c) 상태가 여러 경로에서 재등장하므로 겹치는
부분 문제 도 만족합니다.

복잡도

상태가 \(N \times W\)개, 전이가 \(O(1)\)이므로

$$ O(N \cdot W) $$

이것은 입력 크기 \(N\)에 대해서는 다항이지만 용량 \(W\)의 값 에 비례하므로
엄밀히는 의사 다항(pseudo-polynomial)입니다. \(W\)가 아주 크면 이 방법은 못 씁니다.

변형 미리보기

핵심 점화식은 같고, 순회 방향과 갱신 출처 만 달라집니다. 다음 강의에서
1차원 배열로 압축하는 핵심 기교와 변형 구현을 봅니다.

2차원 → 1차원 압축

dp[i][c]는 dp[i-1][...]만 참조하므로 한 줄만 있으면 됩니다. 핵심은
순회 방향 입니다.

0/1 배낭: 용량을 큰 쪽에서 작은 쪽으로

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, W; cin >> n >> W;
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; i++) {
        int w, v; cin >> w >> v;
        for (int c = W; c >= w; c--)   // 거꾸로: 같은 물건 중복 방지
            dp[c] = max(dp[c], dp[c - w] + v);
    }
    cout << dp[W] << '\n';
}

c를 내림차순 으로 도는 이유: dp[c - w]가 아직 이번 물건으로 갱신되지
않은 "이전 줄"의 값이어야 하기 때문입니다. 오름차순으로 돌면 같은 물건을 여러
번 넣게 됩니다 — 그것이 바로 완전 배낭이 됩니다.

완전(무한) 배낭: 용량을 작은 쪽에서 큰 쪽으로

for (int c = w; c <= W; c++)        // 오름차순: 같은 물건 재사용 허용
    dp[c] = max(dp[c], dp[c - w] + v);

방향 하나로 0/1과 완전 배낭이 갈린다는 점이 이 단원의 핵심 직관입니다.

파이썬 (0/1 배낭)

import sys
input = sys.stdin.readline

n, W = map(int, input().split())
dp = [0] * (W + 1)
for _ in range(n):
    w, v = map(int, input().split())
    for c in range(W, w - 1, -1):    # 거꾸로
        dp[c] = max(dp[c], dp[c - w] + v)
print(dp[W])

개수 제한 배낭 — 이진 분할

물건 \(i\)를 최대 \(k\)개 쓸 수 있으면, \(k\)를 \(1, 2, 4, \dots\) 묶음으로 쪼개
여러 개의 0/1 물건으로 바꿉니다. \(k=11\)이면 \(1, 2, 4, 4\) 묶음으로
모든 개수 0..11을 표현할 수 있습니다. 복잡도는 \(O(N \cdot W \cdot \log k)\).

for (int cnt = 1; k > 0; cnt <<= 1) {
    int take = min(cnt, k);          // 마지막 묶음 보정
    int ww = take * w, vv = take * v;
    for (int c = W; c >= ww; c--)
        dp[c] = max(dp[c], dp[c - ww] + vv);
    k -= take;
}

흔한 함정

• 순회 방향 혼동 — 0/1인데 오름차순으로 돌면 같은 물건을 중복 사용해
  오답이 됩니다. 1차원 배낭에서 가장 잦은 실수입니다.
• 개수/가치 자료형 — 가치 합이 클 수 있으면 long long.
• "정확히 W" vs "W 이하" — dp[W]만 답이 아니라 max(dp)가 답일 때도
  있습니다. 초기화도 달라집니다("정확히" 채우려면 도달 불가를 \(-\infty\)로).

응용 패턴

• 부분집합 합 / 동전 거스름 — 가치 대신 가능 여부(bool)나 경우의 수를 DP.
• 두 그룹으로 분할 — 합의 절반 용량 배낭.
• 무게가 작고 가치가 큰 경우 — 상태를 "가치 → 최소 무게"로 뒤집어 \(O(N\cdot V)\)로.

배낭은 거의 모든 "고른다/안 고른다 + 자원 제약" 문제의 원형입니다. 점화식과
순회 방향만 분명히 잡으면 변형은 자연스럽게 따라옵니다.

출제 신호

문제에서 이런 표현이 보이면 배낭 DP를 먼저 떠올립니다.

• "무게(비용)가 \(w_i\), 가치가 \(v_i\)인 물건 \(N\)개" + "용량 \(K\)를 넘지 않게 골라라"
• "각 물건은 한 번만" → 0/1 배낭, "여러 번 사용 가능" → 무한 배낭
• "정확히 \(K\)를 만들 수 있는가 / 만드는 경우의 수" → 부분합(배낭의 카운팅 변형)

제약 모양이 결정적입니다. \(N \le 100{\sim}1000\), \(K \le 10^4{\sim}10^5\) 이고
\(N \times K\)가 \(10^7{\sim}10^8\) 안쪽이면 거의 확실히 \(O(NK)\) 배낭입니다.
반대로 \(K \le 10^9\) 처럼 용량이 너무 크면 배낭이 아니라 그리디·이분 탐색,
혹은 "가치 축으로 DP"(\(\sum v_i\)가 작을 때) 같은 축 교체를 의심해야 합니다.

풀이 결정 절차

1. 무엇이 상태인가? — "지금까지 쓴 용량 \(j\)"가 상태, 답은 dp[j] = 최대 가치.
2. 물건당 횟수는? — 1번(0/1) / 무제한(unbounded) / \(c_i\)번(개수 제한)을 먼저 확정합니다.
3. 복잡도 검산 — \(N \times K\) 곱을 직접 계산해 봅니다. \(10^8\) 초과면 1초 안에 어렵습니다.
4. 목표가 최대 가치인가, 경우의 수인가, 가능 여부인가? — 점화식은 같고
   max를 +(카운팅)나 or(가능성)로 바꾸면 됩니다.
5. 개수 제한 \(c_i\)가 크면 이진 분할(1, 2, 4, ... 개 묶음)로 0/1 배낭으로 환원합니다.

자주 하는 실수

가장 많이 틀리는 곳은 1차원 배열의 순회 방향입니다. 0/1 배낭에서 용량을
오름차순으로 돌리면 같은 물건이 한 턴에 여러 번 들어갑니다.

// 0/1 배낭: 반드시 내림차순 (같은 물건 재사용 차단)
for (int i = 0; i < n; i++)
    for (int j = K; j >= w[i]; j--)
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

// 무한 배낭: 반대로 오름차순 (재사용이 곧 의도)
for (int i = 0; i < n; i++)
    for (int j = w[i]; j <= K; j++)
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

방향 하나로 문제의 종류가 바뀌니, 제출 전에 꼭 자문해 보세요.
"이 루프 방향이 내 문제의 '한 번만/여러 번' 조건과 맞는가?"

그다음으로 잦은 실수 두 가지입니다.

• "정확히 \(j\)" vs "최대 \(j\)" 초기화 혼동 — "정확히 채우기"는 dp[0]=0,
  나머지를 \(-\infty\)로 둬야 합니다. 전부 0으로 초기화하면 "\(j\) 이하"가 됩니다.

NEG = float('-inf')
dp = [NEG] * (K + 1)
dp[0] = 0          # 정확히 0을 만드는 가치 0에서만 출발

• 카운팅 변형의 오버플로/모듈러 누락 — 경우의 수는 금방 커집니다. 문제에
  모듈러가 있으면 매 갱신마다 % MOD, 없으면 long long이나 파이썬 정수를 씁니다.

연습 방법

사이드바의 연습 문제 목록을 쉬운 것부터 차례로 푸세요. 순수 0/1 배낭
한 문제로 점화식을 손에 익히고, 그다음에 무한 배낭·카운팅·"정확히 채우기"
변형을 하나씩 추가하는 순서가 좋습니다. 각 문제마다 코드를 보기 전에
"상태 / 횟수 제한 / 루프 방향" 세 가지를 종이에 먼저 적는 습관을 들이면
변형 문제에서 흔들리지 않습니다. 태그가 달린 문제를 3문제 이상 해결하면
이 알고리즘이 마스터 처리되어 레이팅의 CLASS 보너스에 반영됩니다.