Задача о рюкзаке: динамическое программирование

Задача о рюкзаке - классический пример, которым открывают курс динамического программирования в дискретной математике и алгоритмах. Постановка проста: есть $n$ предметов с весами $w_1, \ldots, w_n$ и ценностями $v_1, \ldots, v_n$, и рюкзак вместимостью $W$. Нужно выбрать подмножество предметов так, чтобы суммарный вес не превысил $W$, а суммарная ценность была максимальной. Перебор всех $2^n$ подмножеств здесь не подходит уже при $n = 30$, и именно ДП сводит задачу к $O(n \cdot W)$ операциям.

Идея динамического программирования

Ключевой принцип ДП - разбить большую задачу на перекрывающиеся подзадачи и сохранить их результаты. Для рюкзака подзадача - это «максимальная ценность при первых $i$ предметах и вместимости $w$». Обозначим её $dp[i][w]$.

Чтобы найти $dp[i][w]$, у нас ровно два варианта:

1. Не брать $i$-й предмет - тогда $dp[i][w] = dp[i-1][w]$.
2. Взять $i$-й предмет (возможно только если $w_i \le w$) - тогда $dp[i][w] = dp[i-1][w - w_i] + v_i$.

Отсюда рекуррентное соотношение:

$$dp[i][w] = \begin{cases} dp[i-1][w], & w_i > w, \\ \max\!\bigl(dp[i-1][w],\; dp[i-1][w - w_i] + v_i\bigr), & w_i \le w. \end{cases}$$

Начальные условия: $dp[0][w] = 0$ для всех $w$ (нет предметов - нет ценности) и $dp[i][0] = 0$ для всех $i$ (рюкзак пуст - нечего класть).

Пример заполнения dp-таблицы

Возьмём учебный набор из 4 предметов:

Вместимость $W = 7$. Начинаем с нулевой строки (все нули) и заполняем строку за строкой:

Рассчитать для своей задачи

Для строки «часы» (вес 1, ценность 2) при $w = 3$: $dp[4][3] = \max(dp[3][3],\; dp[3][2] + 2) = \max(4,\; 3 + 2) = 5$. Берём часы.

Итоговая таблица (строки - предметы, столбцы - вместимость от 0 до 7):

$$dp[4][7] = 9$$

Это и есть оптимальная ценность при вместимости 7.

Восстановление оптимального набора (traceback)

Таблица $dp$ хранит только значения, а не сами выборы. Чтобы узнать, какие предметы вошли в набор, идём по таблице с конца:

1. Начинаем с $i = n$, $w = W$.
2. Если $dp[i][w] \ne dp[i-1][w]$ - предмет $i$ взят. Переходим к $i-1$, $w \leftarrow w - w_i$.
3. Иначе - предмет $i$ не взят. Переходим к $i-1$, $w$ не меняем.
4. Повторяем до $i = 0$.

Рассчитать для своей задачи

Для нашего примера traceback при $W = 7$: берём часы ($dp[4][7] \ne dp[3][7]$, $w = 6$), берём камеру ($dp[3][6] \ne dp[2][6]$, $w = 3$), не берём ноутбук, берём книгу ($dp[1][3] \ne dp[0][3]$). Итого: книга + камера + часы, ценность $3 + 4 + 2 = 9$, вес $2 + 3 + 1 = 6 \le 7$.

Канонический inline-кадр: traceback в таблице

Рассчитать для своей задачи

На inline-кадре видно, что traceback идёт по «синим» ячейкам (где $dp[i][w] > dp[i-1][w]$) - это строки, в которых предмет был включён в рюкзак. Золотые рамки отмечают конкретный путь при $W = 7$.

Сложность алгоритма

Временная сложность - $O(n \cdot W)$: два вложенных цикла по $n$ предметам и $W + 1$ значениям вместимости. Пространственная - тоже $O(n \cdot W)$ для хранения всей таблицы.

При обходе справа налево для одного массива dp[w]:

$$dp[w] \leftarrow \max(dp[w],\; dp[w - w_i] + v_i), \quad w = W, W-1, \ldots, w_i.$$

Направление справа налево гарантирует, что $dp[w - w_i]$ ещё не обновлялось на текущей итерации - то есть берётся значение из «предыдущей строки».

Ограничения метода: псевдополиномиальность

Важный нюанс: хотя сложность $O(n \cdot W)$ выглядит полиномиальной, на самом деле $W$ - числовое значение (не количество битов для его записи). Алгоритм называют псевдополиномиальным: при $W = 2^{64}$ он неприменим. Для таких задач используют ветви и границы или аппроксимационные схемы (FPTAS).

Вариации задачи

Неограниченный рюкзак (unbounded knapsack): каждый предмет можно брать сколько угодно раз. Переход меняется: $dp[i][w] = \max(dp[i-1][w],\; dp[i][w - w_i] + v_i)$ - обратите внимание, что теперь строка $i$, а не $i-1$ в варианте «взять предмет».

Рюкзак с точной вместимостью: нужно заполнить рюкзак ровно до $W$. Инициализируем $dp[0][0] = 0$, $dp[0][w] = -\infty$ для $w > 0$.

Мультидимензиональный рюкзак: несколько ограничений (вес и объём). Таблица становится трёхмерной: $dp[i][w][v]$.

Задача о сумме подмножества (subset sum): частный случай, где $v_i = w_i$ и нужно набрать ровно $W$.

Частые ошибки

• Обход слева направо при оптимизации памяти - предмет может войти несколько раз (превращается в unbounded knapsack). Нужен обход справа налево.
• Инициализация ненулевыми значениями - нулевая строка и нулевой столбец должны быть нулями; иначе traceback ломается.
• Путаница индексов - в коде удобно хранить $dp[i][w]$ с 1-индексацией предметов, но при трансляции из 0-индексированных массивов языка легко ошибиться.
• Попытка применить жадный алгоритм - сортировка по удельной ценности не даёт оптимума для целочисленного рюкзака. Стандартный контрпример: предметы $(3, 4)$ и $(1, 2)$ при $W = 2$: жадный возьмёт предмет 2 ($v/w = 2$) и получит ценность 2, а ДП возьмёт предмет 1 ($v/w = 4/3$... нет, $v=4 > W=2$, берётся предмет 2). Возьмём другой: $(5,10)$, $(4,8)$, $(3,7)$ при $W=7$: жадный выберет $(5,10)+(2$ невлезет$)$ и $v=10$; ДП выберет $(4,8)+(3,7)=15$.
• Забыть traceback - таблица даёт только оптимальную ценность; набор предметов нужно восстанавливать отдельно.

FAQ

Чем ДП-решение рюкзака отличается от жадного? Жадный алгоритм принимает локально оптимальное решение на каждом шаге (берём предмет с наибольшим $v_i/w_i$), и для целочисленного рюкзака это может дать субоптимальный ответ. ДП перебирает все комбинации неявно через рекуррентное соотношение и гарантирует глобальный оптимум.

Почему алгоритм называют псевдополиномиальным? Потому что сложность $O(n \cdot W)$ зависит от числового значения $W$, а не от длины его двоичной записи ($\log W$). Если $W$ задаётся $k$ битами, то «реальная» сложность - $O(n \cdot 2^k)$, что является экспоненциальной. При малых или умеренных $W$ алгоритм очень быстр на практике.

Как решить задачу о рюкзаке для дробных объёмов? Если $w_i$ и $W$ - рациональные числа, умножаем все веса на наименьшее общее кратное знаменателей, чтобы перейти к целым числам, и применяем стандартный алгоритм ДП. Если точность не критична - округляем веса до нужного числа знаков и масштабируем.

Коротко

Задача о рюкзаке в постановке 0/1 решается динамическим программированием за $O(n \cdot W)$ времени: строим таблицу $dp[i][w]$ снизу вверх по рекуррентному соотношению, а затем восстанавливаем оптимальный набор обратным проходом (traceback). Оптимизация памяти до $O(W)$ возможна при обходе столбцов справа налево. Алгоритм псевдополиномиален - применим, пока $W$ не слишком велико.