핵심 정리
| 조건 | 내용 |
|---|---|
| 문제 | 용량 안에서 가치 합 최대화 |
| 0/1 의미 | 각 물건은 고르거나 안 고름 |
| 2차원 상태 | dp[i, w]: i번째까지, 용량 w |
| 1차원 압축 | 용량을 큰 값에서 작은 값으로 순회 |
| 시간 | O(NW) |
csharp
int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++)
{
int weight = weights[i];
int value = values[i];
for (int w = capacity; w >= weight; w--)
{
dp[w] = Math.Max(dp[w], dp[w - weight] + value);
}
}구조
0/1 Knapsack은 각 물건을 한 번만 사용할 수 있는 DP입니다. i번째 물건을 보면서 “넣지 않는 경우”와 “넣는 경우” 중 더 큰 값을 고릅니다.
text
넣지 않음: dp[i - 1, w]
넣음: dp[i - 1, w - weight[i]] + value[i]2차원 DP는 의미를 추적하기 쉽습니다. 다만 N * W만큼 메모리를 쓰므로 용량이 크면 1차원 압축을 검토합니다.
csharp
for (int i = 1; i <= n; i++)
{
for (int w = 0; w <= capacity; w++)
{
dp[i, w] = dp[i - 1, w];
if (w >= weights[i - 1])
{
dp[i, w] = Math.Max(
dp[i, w],
dp[i - 1, w - weights[i - 1]] + values[i - 1]);
}
}
}반복 방향
1차원 압축에서 용량을 큰 값에서 작은 값으로 내려가는 이유는 같은 물건을 같은 반복 안에서 두 번 쓰지 않기 위해서입니다.
text
내림차순:
dp[w - weight]는 이전 물건까지만 반영된 값
오름차순:
방금 갱신한 dp[w - weight]를 다시 써서 같은 물건을 여러 번 고를 수 있음무한히 같은 물건을 고를 수 있는 unbounded knapsack은 반대로 용량을 작은 값에서 큰 값으로 순회합니다. 반복 방향이 문제 조건을 표현합니다.
주의할 점
복잡도는 물건 수와 용량의 곱입니다. N = 100, W = 100000 정도는 가능할 수 있지만, 용량이 10억이면 배열 DP로 풀 수 없습니다. 이때는 가치 기준 DP, meet-in-the-middle, branch and bound 같은 다른 접근을 검토해야 합니다.
또 물건을 정확히 채워야 하는 문제라면 기본값 0이 모든 용량을 가능한 상태로 만들어 버릴 수 있습니다. 불가능 상태는 충분히 작은 값으로 초기화하고 시작 상태만 0으로 둡니다.
참고 링크
1 sources