Динамическое программирование: рюкзак, который научил машины не считать дважды

За пугающим названием «динамическое программирование» прячется детская идея: посчитал что-то один раз — запиши и больше не пересчитывай.

Ричард Беллман признавался, что выбрал слово «динамическое» отчасти потому, что оно звучало солидно и не вызывало подозрений у министра обороны, не любившего слово «исследование».

Задача о рюкзаке

У вора рюкзак, выдерживающий $W$ килограммов. Перед ним предметы, у каждого свой вес и своя ценность. Какой набор предметов унести, чтобы суммарная ценность была максимальной и рюкзак не порвался? Это классическая задача о рюкзаке (knapsack), и в ней удивительно много прикладного: так распределяют бюджет по проектам, грузят контейнеры, нарезают рекламные слоты.

Почему перебор взрывается

Можно перебрать все подмножества предметов: каждый либо берём, либо нет. Для $n$ предметов это $2^n$ вариантов. Для 50 предметов — больше квадриллиона комбинаций, перебор не закончится за разумное время. Нужен способ не трогать заведомо лишнее. И тут выясняется, что многие подзадачи в этом переборе повторяются.

Два признака, что подойдёт ДП

Динамическое программирование работает, когда у задачи есть два свойства. Первое — оптимальная подструктура: оптимальное решение целой задачи складывается из оптимальных решений её частей. Второе — перекрывающиеся подзадачи: при наивном решении одни и те же подзадачи считаются многократно. Если оба признака есть, можно считать каждую подзадачу ровно один раз, сохранять результат в таблицу и переиспользовать. Это и есть весь метод.

Рекуррента для рюкзака

Обозначим за $dp[i][w]$ максимальную ценность, которую можно набрать из первых $i$ предметов при лимите веса $w$. Для очередного предмета есть выбор: не брать его (тогда ответ как для $i-1$ предметов) или взять, если он влезает (тогда прибавляем его ценность к лучшему решению для оставшегося веса). Берём максимум:

$$dp[i][w] = \max\big(dp[i-1][w],\; dp[i-1][w - w_i] + v_i\big)$$

Второй вариант применим только при $w_i \le w$. Заполняя таблицу снизу вверх, мы вычисляем каждую клетку один раз, опираясь на уже посчитанные.

def knapsack(weights, values, capacity):
    n = len(weights)
    # dp[i][w] = макс. ценность из первых i предметов при лимите w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wi, vi = weights[i - 1], values[i - 1]
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]               # вариант: не берём предмет
            if wi <= w:                           # если влезает —
                take = dp[i - 1][w - wi] + vi     # пробуем взять
                if take > dp[i][w]:
                    dp[i][w] = take
    return dp[n][capacity]

weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
print(knapsack(weights, values, 5))   # 7 (предметы весом 2 и 3)
print(knapsack(weights, values, 8))   # 10

Сколько это стоит

Таблица имеет размер $n \times W$, и каждая клетка считается за константу. Значит, сложность $O(n \cdot W)$ — мы заменили экспоненциальный взрыв $2^n$ на произведение двух чисел. Для 50 предметов и лимита в тысячу это пятьдесят тысяч операций вместо квадриллиона. Тонкость: это псевдополиномиальная сложность — она зависит от числового значения $W$, а не только от размера входа. Для гигантских весов таблица всё же раздувается, и задача в общем виде остаётся NP-трудной. Но для практических лимитов ДП решает её мгновенно.

Где встречается динамика

Рюкзак — лишь витрина. На том же принципе «не считай дважды» стоят расстояние Левенштейна (как автокоррект понимает, что вы хотели написать), выравнивание ДНК-последовательностей в биоинформатике, оптимальное размещение скобок при умножении матриц, кратчайшие пути (алгоритм самого Беллмана — Форда) и сотни олимпиадных задач. ДП — не алгоритм, а способ мышления, применимый к огромному классу задач оптимизации.

Мораль

Динамическое программирование звучит грозно, а сводится к дисциплине: разложи задачу на подзадачи, заметь, что они повторяются, и заведи таблицу ответов. Самое трудное здесь — не код, а увидеть рекурренту: правильно сформулировать, что значит «оптимально для части». Научишься этому — и целый пласт «невозможных» переборных задач превратится в аккуратное заполнение таблицы.