Quick Flow
| 조건 | 내용 |
|---|---|
| 문제 | 용량 안에서 가치 합 최대화 |
| 0/1 의미 | 각 물건은 고르거나 안 고름 |
| 2차원 상태 | dp[i, w]: i번째까지, 용량 w |
| 1차원 압축 | 용량을 큰 값에서 작은 값으로 순회 |
| 시간 | O(NW) |
int[] weights = { 2, 3, 4 };
int[] values = { 4, 5, 7 };
long bestValue = MaxValue01(weights, values, capacity: 5); // 9각 물건을 한 번만 고르면 0/1 배낭이며, 1차원 DP는 용량을 큰 쪽에서 작은 쪽으로 갱신합니다. 반대로 돌리면 같은 물건을 반복 선택하게 됩니다.
구조
0/1 Knapsack은 각 물건을 한 번만 사용할 수 있는 DP입니다. i번째 물건을 보면서 “넣지 않는 경우”와 “넣는 경우” 중 더 큰 값을 고릅니다.
넣지 않음: dp[i - 1, w]
넣음: dp[i - 1, w - weight[i]] + value[i]2차원 DP는 의미를 추적하기 쉽습니다. 다만 N * W만큼 메모리를 쓰므로 용량이 크면 1차원 압축을 검토합니다.
static long MaxValue01(
IReadOnlyList<int> weights,
IReadOnlyList<int> values,
int capacity)
{
if (weights.Count != values.Count || capacity < 0)
{
throw new ArgumentException("물건 수와 용량을 확인하세요.");
}
var dp = new long[capacity + 1];
for (int i = 0; i < weights.Count; i++)
{
if (weights[i] <= 0) throw new ArgumentOutOfRangeException(nameof(weights));
for (int weight = capacity; weight >= weights[i]; weight--)
{
dp[weight] = Math.Max(dp[weight], dp[weight - weights[i]] + values[i]);
}
}
return dp[capacity];
}weights.Count == values.Count, 모든 weight가 양수, capacity >= 0이 이 코드의 입력 계약입니다. 선택한 물건 자체가 필요하면 2차원 DP를 유지해 dp[i, w] != dp[i - 1, w]인 지점을 거꾸로 따라가며 w -= weights[i - 1]로 복원합니다. 1차원 압축은 메모리를 줄이는 대신 이 정보를 바로 잃습니다.
static List<int> PickItems01(
IReadOnlyList<int> weights,
IReadOnlyList<int> values,
int capacity)
{
if (weights.Count != values.Count || capacity < 0)
{
throw new ArgumentException("물건 수와 용량을 확인하세요.");
}
var dp = new long[weights.Count + 1, capacity + 1];
for (int i = 1; i <= weights.Count; i++)
{
if (weights[i - 1] <= 0) throw new ArgumentOutOfRangeException(nameof(weights));
for (int weight = 0; weight <= capacity; weight++)
{
dp[i, weight] = dp[i - 1, weight];
if (weight >= weights[i - 1])
{
dp[i, weight] = Math.Max(
dp[i, weight],
dp[i - 1, weight - weights[i - 1]] + values[i - 1]);
}
}
}
var pickedIndices = new List<int>();
for (int i = weights.Count, weight = capacity; i > 0; i--)
{
if (dp[i, weight] == dp[i - 1, weight]) continue;
pickedIndices.Add(i - 1);
weight -= weights[i - 1];
}
pickedIndices.Reverse();
return pickedIndices;
}같은 최대 가치가 여러 조합에서 나올 수 있을 때 이 함수는 넣지 않음과 값이 같은 경우를 우선해 그중 하나를 반환합니다. 선택한 물건의 순서나 개수를 별도 기준으로 최적화하는 문제는 상태에 tie-breaker를 추가해야 합니다.
반복 방향
1차원 압축에서 용량을 큰 값에서 작은 값으로 내려가는 이유는 같은 물건을 같은 반복 안에서 두 번 쓰지 않기 위해서입니다.
내림차순:
dp[w - weight]는 이전 물건까지만 반영된 값
오름차순:
방금 갱신한 dp[w - weight]를 다시 써서 같은 물건을 여러 번 고를 수 있음무한히 같은 물건을 고를 수 있는 unbounded knapsack은 반대로 용량을 작은 값에서 큰 값으로 순회합니다. 반복 방향이 문제 조건을 표현합니다.
주의할 점
복잡도는 물건 수와 용량의 곱인 pseudo-polynomial 비용입니다. 용량의 숫자값이 커지면 배열 DP는 입력 길이에 비해 급격히 커질 수 있습니다. 이때는 가치 기준 DP, meet-in-the-middle, branch and bound 같은 다른 접근을 검토해야 합니다.
또 물건을 정확히 채워야 하는 문제라면 기본값 0이 모든 용량을 가능한 상태로 만들어 버릴 수 있습니다. 불가능 상태는 충분히 작은 값으로 초기화하고 시작 상태만 0으로 둡니다.
참고 링크
1 sources