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

Есть рюкзак (knapsack) вместимости $W$, а также $n$ предметов веса $w_{1}, \ldots, w_{n}$ и стоимости $p_{1}, \ldots, p_{n}$. Необходимо поместить в рюкзак множество предметов как можно большей суммарной стоимости. Более формально, нужно найти такое подмножество предметов $A \subset\{1, \ldots, n\}$, что $\sum_{i \in A} w_{i} \leqslant W$, а значение $\sum_{i \in A} p_{i}$ максимально возможно.

Существует много различных вариаций этой задачи. Можно, например, считать, что есть лишь одна копия каждого предмета (версия “без повторений”), а можно - что копий каждого предмета бесконечно много (версия “с повторениями”).

Версия “с повторениями”

Пусть $k[j]$ - максимальная возможная суммарная стоимость, если рюкзак имеет вместимость $j$. Начальное состояние: $k[0]=0$. Переход заключается в выборе последнего взятого предмета:

(максимум по пустому множеству считаем равным нулю). Ответ на задачу $-\max _{0 \leqslant j \leqslant W} k[j]$. Получаем решение за $O(n W)$ с $O(W)$ дополнительной памяти. Восстановление ответа делается стандартными методами.

1
2
3
4
5

fill(k, 0)
for j = 0..W:
    for i = 1..n:
        if w[i] <= j:
            k[j] = max(k[j], k[j - w[i]] + p[i])

Версия “без повторений”

Для того, чтобы не взять один предмет несколько раз, введём дополнительный параметр. Пусть $k[i, j]$ - максимальная возможная суммарная стоимость, если разрешается брать только предметы с номерами не больше $i$, а рюкзак имеет вместимость $j$. Начальные состояния: $k[0, j]=k[i, 0]=0$. Переход: либо $i$-й предмет входит в ответ (то есть $k[i, j]=k\left[i-1, j-w_{i}\right]$; этот вариант возможен только при $j \geqslant w_{i}$ ), либо не входит (то есть $k[i, j]=k[i-1, j])$. Получаем решение за $O(n W)$ с такой же оценкой используемой дополнительной памяти. .

1
2
3
4
5
6

fill(k, 0)
for i = 1..n:
    for j = 0..W:
        k[i, j] = k[i - 1, j]
        if w[i] <= j:
            k[i, j] = max(k[i, j], k[i - 1, j - w[i]] + p[i])

Оптимизация памяти

Заметим, что при вычислении $k[i, j]$ алгоритму могут понадобиться только значения $k[i-1, q]$ с $q \leqslant j$. Сделаем следующий трюк: будем вычислять значения $k[i, j]$ при фиксированном $i$ в порядке убывания $j$ (а не возрастания, как раньше). Тогда можно обойтись одномерным массивом: при обработке состояния $(i, j)$ в $k[0 . . j]$ будем хранить значения $k[i-1,0], \ldots, k[i-1, j]$, а в $k[j+1 . . W]$ - значения $k[i, j+1], \ldots, k[i, W]$. Получается, достаточно $O(W)$ дополнительной памяти. При этом получившийся код отличается от решения версии задачи “с повторениями” только порядком перебора значений $j$.

fill(k, 0)
for i = 1..n:
    for j = W..O:
        if w[i] <= j:
            k[j] = max(k[j], k[j - w[i]] + p[i])

Восстановление ответа

В версии с двумерным массивом восстановление ответа делается стандартными методами. В версии с одномерным массивом ответ просто так восстановить не удастся; зато можно применить идею алгоритма Хиршберга и восстановить ответ, используя $O(W+\log n)$ дополнительной памяти, и не ухудшив оценку времени работы.