Следующим обобщением задачи про золотые слитки является «задача об укладке рюкзака».
В этой задаче также имеется несколько предметов, для каждого предмета заданы две характеристики: вес wi > 0 и стоимость («полезность»)
предмета pi > 0.
Необходимо выбрать множество предметов суммарной максимальной стоимости, при этом суммарная масса выбранных предметов должна быть
ограничена значением K.
Одним из способов решения этой задачи является полный перебор всех подмножеств из n предметов, которых будет 2^n и выбор среди
них наилучшего подмножества, удовлетворяющего условиям задачи.
Такой алгоритм будет иметь сложность O(2^n).
Если же массы всех предметов являются целыми числами (так называемая «дискретная» задача), то в данном случае возможно придумать
решение сложности O(nK) при помощи динамического программирования.
Как и в задаче про золотые слитки, будем для каждой возможной массы k хранить информацию о способе набора этой массы, но в отличии
от задачи про слитки будем хранить не возможность набора данной массы (0 или 1), а наилучшее решение для данной массы, то есть
наибольшую стоимость предметов, которые можно набрать в рюкзак данной массы.
Формально определим так: F(i, k) - максимальная стоимость предметов, которые можно уложить в рюкзак массы k, если можно использовать
только первые i предметов.
Выведем рекуррентное соотношение для F(i, k) уменьшив значение i.
Есть две возможности собрать рюкзак, используя первые i предметов - взять предмет с номером i или не брать.
Если не брать предмет с номером i, то в этом случае F(i, k) = F(i − 1, k), так как рюкзак массы k будет собран только с использованием
первых i − 1 предмета.
В этом случае F(i, k) = F(i − 1, k).
Если же предмет номер i войдет в рюкзак (это можно сделать только при k ≥ wi), то останется свободная вместимость рюкзака k − wi,
которую можно будет заполнить первыми i − 1 предметом, максимальная стоимость рюкзака в этом случае будет F(i − 1, k − wi).
Но поскольку предмет номер i был включен в рюкзак, то стоимость рюкзака увеличится на pi.
То есть в этом случае F(i, k) = F(i − 1, k − wi) + pi.
Из двух возможных вариантов нужно выбрать вариант наибольшей стоимости, то есть F(i, k) = max(F(i − 1, k), F(i − 1, k − wi) + pi).
Для хранения значения функции F будем использовать двумерный список.
При этом массы предметов хранятся в списке W, их стоимости - в списке P.
Будем считать (для простоты записи программы), что предметы пронумерованы от 1 до n.
F = [ [0] * (K + 1) for i in range(n + 1)]
for i in range(1, n + 1):
for k in range(1, K + 1):
if k >= W[i]:
F[i][k] = max(F[i - 1][k], F[i - 1][k - W[i]] + P[i])
else:
F[i][k] = F[i - 1][k]
Для восстановления ответа будем перебирать все предметы «с конца» от n до 1.
В переменной k будет храниться текущая вместимость рюкзака.
Рассматривая предмет номер i определим, как было получено значение F(i, k).
Если F(i, k) = F(i − 1, k), то можно не включать предмет i в рюкзак и перейти к предмету i − 1 не меняя значения k.
Иначе предмет i нужно включить в рюкзак, при этом значение k уменьшается на wi.
k = K
for i in range(n, 0, -1):
if F[i][k] != F[i - 1][k]:
Ans.append(i)
k -= W[i]
В этой реализации случай, когда F(i, k) = F(i − 1, k) просто пропускается, и рассматривается только случай F(i, k) ≠ F(i − 1, k).
После окончания алгоритма в списке Ans будут храниться номера предметов, входящих в рюкзак.