Как решать задачи 0 1 knapsack?
На этой странице
0/1 Knapsack - классический DP-паттерн выбора предметов: каждый предмет можно взять или не взять. State обычно зависит от индекса предмета и оставшейся вместимости.
Вопрос
Как решать задачу 0/1 knapsack и как сократить память до одномерного массива?
Формулировка
Есть предметы:
weights[i], values[i]Есть вместимость capacity.
Нужно получить максимальную ценность, взяв каждый предмет максимум один раз.
Пример:
weights = [1, 2, 3]
values = [6, 10, 12]
capacity = 5Жадный выбор по "ценности за килограмм" (6, 5, 4) возьмет предметы 1 и 2: вес 3, ценность 16. Третий уже не влезет. Но лучше взять предметы 2 и 3: вес 5, ценность 22. Поэтому нужен DP, который сравнивает варианты.
State
dp[i][w] = максимум ценности, используя первые i предметов и вместимость wTransition
Не берем предмет:
dp[i][w] = dp[i - 1][w]Берем предмет, если помещается:
dp[i][w] = dp[i - 1][w - weight] + valueРеализация
function knapsack(weights: number[], values: number[], capacity: number): number {
const n = weights.length
const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0))
for (let i = 1; i <= n; i++) {
const weight = weights[i - 1]
const value = values[i - 1]
for (let w = 0; w <= capacity; w++) {
dp[i][w] = dp[i - 1][w]
if (weight <= w) {
dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weight] + value)
}
}
}
return dp[n][capacity]
}Таблица для примера выше (строка - сколько первых предметов можно использовать, столбец - вместимость):
| i \ w | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 предметов | 0 | 0 | 0 | 0 | 0 | 0 |
| + предмет 1 (w1, v6) | 0 | 6 | 6 | 6 | 6 | 6 |
| + предмет 2 (w2, v10) | 0 | 6 | 10 | 16 | 16 | 16 |
| + предмет 3 (w3, v12) | 0 | 6 | 10 | 16 | 18 | 22 |
Как получилось 22 в правом нижнем углу: не брать предмет 3 - это dp[2][5] = 16; взять - это 12 + dp[2][5 - 3] = 12 + 10 = 22. Выбираем максимум.
Time O(n * capacity), space O(n * capacity).
Как сократить память до одномерного массива
Строка i зависит только от строки i - 1, поэтому можно хранить одну строку и обновлять ее на месте:
function knapsack1D(weights: number[], values: number[], capacity: number): number {
const dp = new Array(capacity + 1).fill(0)
for (let i = 0; i < weights.length; i++) {
// Идем от большей вместимости к меньшей!
for (let w = capacity; w >= weights[i]; w--) {
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i])
}
}
return dp[capacity]
}Space становится O(capacity).
Почему цикл идет назад? dp[w - weight] должен быть значением из предыдущей строки, то есть без текущего предмета. При обходе справа налево ячейки левее еще не обновлены. Если идти слева направо, dp[w - weight] уже может включать текущий предмет, и он возьмется дважды:
предмет w1 v6, обход слева направо:
dp[1] = dp[0] + 6 = 6
dp[2] = dp[1] + 6 = 12 <- предмет взят дважды, это уже unbounded knapsackТак что обход вперед - это решение другой задачи, где каждый предмет можно брать сколько угодно раз.
Что отвечать на собеседовании?
0/1 knapsack решается DP, где состояние зависит от номера предмета и оставшейся вместимости. На каждом шаге есть выбор: взять предмет или не взять. Каждый предмет можно взять только один раз, поэтому при переходе смотрим на предыдущую строку i - 1.
Что важно помнить: частые ошибки
- Путать 0/1 knapsack и unbounded knapsack.
- Неправильно идти по capacity при 1D optimization.
- Забывать base row/column.
- Использовать greedy по value/weight, хотя это не всегда корректно.
- Ошибаться в индексах
i - 1.
Мини-шпаргалка
- Choice: take / skip.
- State:
i,capacity. - 2D DP:
O(n * W). - 1D DP:
O(W)памяти, вместимость идет от большей к меньшей. - Каждый предмет один раз.
- Base: нули.
- Greedy не гарантирует ответ.