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

Задача о рюкзаке — эталон дискретной оптимизации, которую динамическое программирование решает точно и быстро.

Задача о рюкзаке: выбрать подмножество предметов с максимальной суммарной ценностью так, чтобы суммарный вес не превысил вместимость $W$.

Постановка

Есть $n$ предметов, у $i$-го вес $w_i$ и ценность $v_i$. Рюкзак выдерживает вес $W$. Решение — двоичный вектор $x\in\{0,1\}^n$ ($x_i=1$ — берём предмет):

$$\max_{x\in\{0,1\}^n}\ \sum_i v_i x_i\quad\text{при}\quad \sum_i w_i x_i\le W.$$

Это целочисленная задача: переменные не непрерывны, а двоичны. Градиент бессмыслен. Наивный перебор всех подмножеств — $2^n$ вариантов: для $n=50$ это уже квадриллион, перебор невозможен.

Почему нельзя «жадно»

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

Динамическое программирование

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

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

Сложность — $O(nW)$ вместо $O(2^n)$. Это псевдополиномиальный алгоритм: быстрый, пока $W$ не астрономический.

Реализация с восстановлением ответа

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

dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for w in range(W + 1):
        dp[i][w] = dp[i - 1][w]                     # не берём предмет i
        if weights[i - 1] <= w:                      # можем взять
            cand = dp[i - 1][w - weights[i - 1]] + values[i - 1]
            if cand > dp[i][w]:
                dp[i][w] = cand

print("Максимальная ценность:", dp[n][W])

# восстановим, какие предметы взяты
w = W
chosen = []
for i in range(n, 0, -1):
    if dp[i][w] != dp[i - 1][w]:
        chosen.append(i - 1)
        w -= weights[i - 1]
chosen.reverse()
print("Взяты предметы (индексы):", chosen)
print("Суммарный вес:", sum(weights[i] for i in chosen))

Вывод:

Максимальная ценность: 15
Взяты предметы (индексы): [0, 1, 3]
Суммарный вес: 10

Оптимум — предметы $0,1,3$ (веса $2+3+5=10$, точно заполнили рюкзак) с ценностью $15$. Жадность по $v/w$ взяла бы предмет $3$ ($v/w=1.6$), затем предмет $0$ — но не нашла бы это идеальное сочетание. ДП же гарантирует оптимум, рассмотрев все подзадачи неявно.

Как работает под капотом

ДП работает благодаря оптимальной подструктуре: оптимальное решение для $i$ предметов и веса $w$ строится из оптимальных решений меньших подзадач. Мы не перебираем $2^n$ подмножеств, а заполняем таблицу из $nW$ ячеек, каждая за $O(1)$ — отсюда $O(nW)$. Восстановление ответа идёт назад по таблице: если $dp[i][w]\ne dp[i-1][w]$, значит предмет $i$ был взят. Аналогичная техника решает кратчайшие пути, выравнивание строк, оптимальное расписание.

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

• Жадность вместо ДП. Для целочисленного рюкзака жадный выбор по $v/w$ не оптимален.
• Огромный $W$. При $W\sim10^{12}$ таблица не влезет — псевдополиномиальность не спасёт, нужны другие методы.
• Забыть восстановление. $dp[n][W]$ даёт только ценность; чтобы узнать какие предметы, идите обратно по таблице.

Итоги

• Рюкзак — целочисленная задача $\max\sum v_i x_i$ при $\sum w_i x_i\le W$, $x\in\{0,1\}^n$.
• ДП решает её точно за $O(nW)$ через таблицу $dp[i][w]=\max(\text{не брать},\text{брать})$.
• Жадность не оптимальна; ответ восстанавливается обратным проходом по таблице.