Целый рюкзак: таблица, переход и восстановление набора

Если ты можешь написать переход рюкзака по памяти и восстановить набор обратным проходом, листай до «Теперь сам».

Как думаешь, что мешало жадности

В разделе 14 на предметах (10, 60), (20, 100), (30, 120) и вместимости 50 жадность по удельной цене дала 160, а оптимум - 220. Причина была названа: взятый предмет меняет не только ЗАПАС места, но и ПРАВИЛА для остальных - после предмета весом 10 вместимость 40, и предметы 20 и 30 вместе уже не влезают.

Прежде чем читать дальше: как превратить эту помеху в параметр?

На что это похоже

Заполнение чемодана с линейкой в руках. Ты не пытаешься угадать весь набор сразу - ты идёшь по вещам по порядку и для каждой отвечаешь на один вопрос: «кладу или нет». Чтобы ответить, достаточно знать, сколько места осталось. Таблица рюкзака - это записанные ответы на этот вопрос для всех вещей и всех возможных остатков места.

Механизм: состояние, переход, таблица

СОСТОЯНИЕ
dp[i][c] = максимальная цена, которую можно набрать,
           рассматривая первые i предметов при вместимости c

состояний (n + 1) × (C + 1), переход O(1) ⇒ цена Θ(n·C)

ПЕРЕХОД: для i-го предмета всего два варианта

не берём:  dp[i−1][c]
берём:     cena[i] + dp[i−1][c − ves[i]]        только если ves[i] <= c

dp[i][c] = max(этих двух)

база: dp[0][c] = 0 - из нуля предметов не набрать ничего

i = 1
while i <= n:
    c = 0
    while c <= C:
        dp[i][c] = dp[i - 1][c]                        # не берём
        if ves[i - 1] <= c:
            s = cena[i - 1] + dp[i - 1][c - ves[i - 1]]
            if s > dp[i][c]:
                dp[i][c] = s                           # берём
        c = c + 1
    i = i + 1

ВОССТАНОВЛЕНИЕ НАБОРА (а не только числа)
идём от dp[n][C] назад:
    dp[i][c] == dp[i−1][c]  → i-й предмет НЕ брали, c не меняем
    иначе                   → брали: записываем его, c уменьшаем на вес

Правило

Целый рюкзак: состояние dp[i][c] - лучшая цена на первых i предметах при вместимости c; переход - максимум из «не берём» и «берём плюс ответ для меньшей вместимости»; база - нулевая строка. Цена Θ(n·C) - это ПСЕВДОПОЛИНОМ: оценка линейна по значению C, а не по длине его записи, поэтому при вместимости в миллиард таблица не помещается ни в память, ни во время. Общий ресурс (место) внесён в состояние - именно поэтому подзадачи независимы. Подчеркнём: оптимальная подструктура у рюкзака есть всегда, это свойство ЗАДАЧИ; жадности не хватало не её, а права передумать. Число лежит в dp[n][C], а сам набор восстанавливается обратным проходом: если dp[i][c] равно dp[i−1][c], предмет не брали.

Разбор: таблица на тех самых трёх предметах

Предметы: A (вес 10, цена 60), B (20, 100), C (30, 120), вместимость 50.

В строке таблицы на самом деле 51 клетка - вместимости от 0 до 50; ниже показаны только круглые столбцы, остальные повторяют соседа слева.

         c=0   c=10  c=20  c=30  c=40  c=50
i=0       0     0     0     0     0     0
i=1 (A)   0    60    60    60    60    60
i=2 (B)   0    60   100   160   160   160
i=3 (C)   0    60   100   160   180   220

Разберём две клетки руками.

dp[2][30]: предмет B (вес 20, цена 100)
    не берём → dp[1][30] = 60
    берём    → 100 + dp[1][10] = 100 + 60 = 160
    max = 160    ← это A + B

dp[3][50]: предмет C (вес 30, цена 120)
    не берём → dp[2][50] = 160
    берём    → 120 + dp[2][20] = 120 + 100 = 220
    max = 220    ← это B + C

Вот где видно, чего не хватало жадности: в клетке dp[3][50] алгоритм СРАВНИВАЕТ набор A + B (160) с набором B + C (220) и выбирает второй. Жадность начала с A - самого «выгодного по удельной цене» - и уже не могла передумать. Динамика рассматривает оба варианта на каждом предмете, и именно за это платит временем.

Теперь восстановим НАБОР:

старт: i = 3, c = 50
dp[3][50] = 220, dp[2][50] = 160 - не равны ⇒ предмет C взят
    c = 50 − 30 = 20, i = 2
dp[2][20] = 100, dp[1][20] = 60 - не равны ⇒ предмет B взят
    c = 20 − 20 = 0, i = 1
dp[1][0] = 0, dp[0][0] = 0 - равны ⇒ предмет A не брали

ответ: B и C, суммарный вес 50, цена 220

Это и есть вторая половина работы: заказчику обычно нужен не «220», а список того, что положить.

Разбор: почему Θ(n·C) - это не полином

Оценка Θ(n·C) выглядит как полином, но считает не то, что обычно: C - это ЗНАЧЕНИЕ вместимости, а длина входа - число цифр в этом значении.

вместимость      таблица (при n = 100)        влезает?
        50               5 000 клеток          мгновенно
    10 000             1 000 000              да
10 000 000         1 000 000 000              нет: это гигабайты и минуты

Вместимость 10 миллионов записывается восемью цифрами - вход крошечный, а таблица гигантская. Такие оценки называют ПСЕВДОПОЛИНОМИАЛЬНЫМИ, и целый рюкзак остаётся NP-трудной задачей: быстрого алгоритма, полиномиального по ДЛИНЕ входа, для него не известно.

Это стоит состыковать с критерием из второй главы. Там сказано: если общий ресурс вносится в состояние только как 2^n-маска, задача скорее всего NP-трудна. У рюкзака ресурс вносится обычным числом - и задача всё равно NP-трудна, потому что само это число может быть астрономическим. Значит критерий звучит аккуратнее: дешёвая динамика получается, когда состояний мало ОТНОСИТЕЛЬНО ДЛИНЫ ВХОДА, а не просто «ресурс выражается числом».

практический вывод
веса в граммах и бюджет в копейках - верный способ сделать задачу неподъёмной.
Если единицы можно огрубить (округлить до 100 грамм), таблица сжимается
во столько же раз - это стандартный приём и честный компромисс

Отдельно стоит знать, что у рюкзака есть и вторая форма таблицы - по ЦЕНЕ вместо веса (dp[i][v] = минимальный вес, которым набирается цена v). Она выгодна, когда цены маленькие, а вместимость огромная: цена становится Θ(n·V). Выбор между двумя формами - это выбор, какой из двух ресурсов внести в состояние.

Что ломается без этого

Первое: перепутать порядок циклов и писать dp[i][c] раньше, чем готова строка i−1. Второе, более коварное: свернуть таблицу в одну строку и обходить вместимость по ВОЗРАСТАНИЮ - тогда один предмет можно взять дважды, и задача молча превращается в другую (рюкзак с повторениями). Про это - отдельный урок главы про память. Третье: забыть проверку ves[i] <= c и прочитать клетку по отрицательному индексу: в Python это чтение С КОНЦА массива, то есть мусор без всякой ошибки. Четвёртое: восстанавливать набор, выбирая «где в строке максимум», вместо обратного прохода по равенству клеток: максимум в строке не говорит, какие предметы в него вошли. (Предметы нулевой цены обратный проход тоже не покажет - для него «взяли» и «не взяли» неразличимы; если такие предметы важны, рядом с таблицей значений держат таблицу решений.) Пятое: считать, что Θ(n·C) всегда приемлемо - вместимость в миллион уже даёт сотни миллионов клеток. Шестое: применять эту таблицу к ДРОБНОМУ рюкзаку: там достаточно жадности по удельной цене, и динамика - лишняя работа.

Зачем это в работе

Рюкзак - это шаблон, под который подходит огромный класс практических задач: выбрать набор работ в релиз при ограниченном времени, набор контейнеров на сервер при ограниченной памяти, набор рекламных позиций при ограниченном бюджете. Полезно узнавать его в условии: «выбрать подмножество», «ограничение на сумму одного ресурса», «максимизировать другую сумму» - это рюкзак, и дальше вопрос только в том, влезает ли n·C. Второе, что стоит унести, - про восстановление: в проде почти всегда нужен не оптимум, а решение, и таблица без обратного прохода отвечает лишь на половину вопроса. Третье - огрубление единиц. Фраза «давайте считать не в рублях, а в сотнях рублей» звучит как небрежность, а на самом деле это осознанное сжатие состояния, уменьшающее таблицу в сто раз при потере точности, которую обычно никто не замечает.

Теперь сам

Предметы: (вес 3, цена 4), (вес 4, цена 5), (вес 2, цена 3), вместимость 6. Заполни таблицу и восстанови набор.

         c=0  c=1  c=2  c=3  c=4  c=5  c=6
i=0       0    0    0    0    0    0    0
i=1 (3,4) 0    0    0    4    4    4    4
i=2 (4,5) 0    0    0    4    5    5    5
i=3 (2,3) 0    0    3    4    5    7    8

i = 3, c = 6: dp[3][6] = 8 ≠ dp[2][6] = 5  ⇒ третий взят, c = 4
i = 2, c = 4: dp[2][4] = 5 ≠ dp[1][4] = 4  ⇒ второй взят, c = 0
i = 1, c = 0: dp[1][0] = 0 = dp[0][0]      ⇒ первый не брали

ответ: предметы (4,5) и (2,3) - вес 6, цена 8

{}                   0 / 0
{(3,4)}              3 / 4
{(4,5)}              4 / 5
{(2,3)}              2 / 3
{(3,4), (2,3)}       5 / 7
{(4,5), (2,3)}       6 / 8      ← максимум
{(3,4), (4,5)}       7 - не влезает