Рюкзак (knapsack)

Эталонная задача ДП: набрать максимум ценности, не превысив грузоподъёмность. Учимся переходу и оптимизации памяти.

Задача о рюкзаке 0/1: даны предметы с весами и ценностями и рюкзак вместимости W; нужно выбрать подмножество предметов с максимальной суммарной ценностью, чьи веса в сумме не превышают W (каждый предмет берётся 0 или 1 раз).

Зачем это нужно

Рюкзак — самая известная задача динамического программирования и образец целого класса задач «выбрать подмножество с ограничением». Полный перебор всех подмножеств — O(2^n) — не проходит уже при n = 40. А жадность (брать самые ценные или самые лёгкие) для рюкзака 0/1 неверна — мы это обсуждали в разделе про жадные алгоритмы. Спасает ДП: оно решает рюкзак за O(n·W). Этот же паттерн «динамика по вместимости/бюджету» встречается в десятках замаскированных формулировок, поэтому рюкзак нужно понимать до автоматизма.

Идея «на пальцах»

Рассмотрим предметы по одному и для каждой возможной вместимости решим: брать текущий предмет или нет? Состояние dp[i][cap] — максимальная ценность, которую можно набрать из первых i предметов при вместимости cap. Переход для предмета i (вес w, ценность v):

• Не берём: ценность та же, что без этого предмета — dp[i−1][cap].
• Берём (если влезает): v + dp[i−1][cap−w] — ценность предмета плюс лучшее на оставшейся вместимости.

Берём максимум из двух вариантов. Это и есть суть ДП: каждое решение «брать/не брать» опирается на уже посчитанные подзадачи.

Наивная двумерная версия

weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
W = 8
n = len(weights)

# dp[i][cap] — макс. ценность из первых i предметов при вместимости cap
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    w, v = weights[i - 1], values[i - 1]
    for cap in range(W + 1):
        dp[i][cap] = dp[i - 1][cap]            # вариант "не берём"
        if cap >= w:                           # если предмет влезает
            dp[i][cap] = max(dp[i][cap], v + dp[i - 1][cap - w])
print("Максимальная ценность:", dp[n][W])

Таблица заполняется построчно: строка i опирается только на строку i−1. В ячейке dp[n][W] — ответ. Сложность по времени — O(n·W), по памяти — тоже O(n·W).

Вывод:

Максимальная ценность: 10

Оптимизация памяти: одномерный массив

Заметь: строка i зависит только от строки i−1. Значит, можно хранить один массив dp[cap] и обновлять его на месте. Но есть тонкость: чтобы каждый предмет учитывался один раз, внутренний цикл по вместимости идёт справа налево (от W к w). Иначе обновлённое dp[cap−w] уже включало бы текущий предмет — и мы бы взяли его дважды.

weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
W = 8
n = len(weights)

dp = [0] * (W + 1)
for i in range(n):
    w, v = weights[i], values[i]
    for cap in range(W, w - 1, -1):      # ВАЖНО: обратный проход!
        dp[cap] = max(dp[cap], dp[cap - w] + v)
print("Максимальная ценность при весе", W, ":", dp[W])

Обратный проход — самая запоминающаяся деталь рюкзака 0/1. Если бы шли слева направо, получили бы другую задачу — рюкзак с неограниченным числом каждого предмета (там как раз нужен прямой проход). Память теперь O(W) вместо O(n·W) — критично при больших n.

Вывод:

Максимальная ценность при весе 8 : 10

Разбор ответа на примере

Почему ответ 10? Предметы: (вес 2, цена 3), (3, 4), (4, 5), (5, 6), рюкзак на 8. Лучший выбор — предметы с весами 3 и 5 (цены 4 и 6): суммарный вес 3+5 = 8 ≤ 8, ценность 4+6 = 10. Любой другой набор в пределах 8 даёт не больше. ДП находит этот оптимум, не перебирая все 2⁴ подмножеств явно.

Варианты рюкзака

Подводные камни

• Направление прохода. 0/1 — справа налево; перепутал — посчитал неограниченный рюкзак. Это ошибка номер один.
• Псевдополиномиальность. Сложность O(n·W) зависит от значения W, а не от его длины в битах; при W = 10^9 это уже не пройдёт — нужны другие подходы.
• Жадность не работает для 0/1 рюкзака — только ДП (для дробного рюкзака жадность как раз верна, не путай).
• Память. Если n·W велико, обязательно используй одномерную версию.

Итог

• Рюкзак 0/1: для каждого предмета и вместимости выбираем максимум из «не брать» и «взять».
• Сложность O(n·W) по времени; память можно ужать до O(W) одномерным массивом.
• В одномерной версии 0/1 проход по вместимости идёт справа налево — иначе предмет учтётся многократно.
• Жадность для 0/1 рюкзака неверна; O(n·W) псевдополиномиальна — при огромном W не пройдёт.