배낭 문제란?
0/1 배낭 문제(0/1 Knapsack)는 무게 한도가 정해진 배낭에, 각각 무게와 가치를 가진 물건들을 골라 담아 가치의 합을 최대로 만드는 문제입니다. 각 물건은 통째로 담거나(1) 안 담거나(0) 둘 중 하나 — 쪼갤 수 없습니다.
물건마다 "담는다/안 담는다" 두 갈래라 완전 탐색은 2ⁿ으로 폭발합니다. 동적 계획법(DP)은 겹치는 부분 문제를 표에 저장해 O(nW)로 줄입니다.
상태 정의
dp[i][w] = 앞에서 i개 물건까지 고려했고, 무게 한도가 w일 때 얻을 수 있는 최대 가치.
이렇게 정의하면, 물건을 하나 더 볼 때 "지금 물건을 담을지"만 결정하면 되도록 문제가 쪼개집니다.
점화식
i번째 물건의 무게가 wt, 가치가 v라면
- •안 담는다:
dp[i-1][w](한도 그대로, 가치 그대로) - •담는다(w ≥ wt일 때):
dp[i-1][w - wt] + v(담은 무게만큼 한도를 빼고 가치 더함) - •
dp[i][w] = max(안 담음, 담음)
두 선택 중 가치가 큰 쪽을 택하는 것이 전부입니다.
동작 원리
1단계. dp[0][*] = 0 (물건이 없으면 가치 0)으로 초기화합니다.
2단계. 물건 i를 하나씩 늘려가며, 모든 무게 한도 w에 대해 위 점화식으로 표를 채웁니다.
3단계. dp[n][W]가 정답(전체 물건, 최대 한도에서의 최대 가치)입니다.
1차원 최적화: dp[w] 한 줄만 두고 w를 큰 값에서 작은 값으로 갱신하면 공간이 O(W)로 줄어듭니다.
알고노트 시각화는 표가 한 칸씩 채워지며 "담음/안 담음" 중 어느 쪽이 선택되는지 단계별로 보여줍니다.
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간 | O(nW) |
| 공간 | O(nW) 또는 O(W) |
n은 물건 수, W는 무게 한도입니다.
예시로 따라가기
물건 (무게, 가치) = (1, 6), (2, 10), (3, 12), 한도 W=5.
- •물건1만: 한도 5에서 가치 6
- •물건1·2: (1,6)+(2,10) 둘 다 담아 무게3·가치16
- •물건1·2·3: (2,10)+(3,12)=무게5·가치22 → 최대 22
dp[3][5] = 22가 정답입니다.
자주 하는 실수
- •1차원 갱신 방향:
dp[w]를 작은 w부터 갱신하면 같은 물건을 여러 번 담게 됩니다(그건 "무한 배낭"). 0/1은 반드시 큰 w부터. - •한도 비교 누락:
w ≥ wt일 때만 담는 분기를 적용해야 음수 인덱스를 피합니다. - •W가 거대할 때: O(nW)가 부담이면 가치 기준 DP 등 다른 정의를 고려합니다.
알고노트에서 직접 확인하세요
각 물건에서 "담음"과 "안 담음" 가치를 비교해 표가 채워지는 과정을 알고노트에서 단계별로 확인할 수 있습니다.