Динамическое программирование. Рюкзак.
| Сайт: | Информатикс |
| Курс: | Зимняя школа в "Эврике" |
| Книга: | Динамическое программирование. Рюкзак. |
| Напечатано:: | Гость |
| Дата: | Пятница, 27 Июнь 2025, 08:28 |
1. Введение.
Пусть имеется набор предметов, каждый из которых имеет два параметра — вес и ценность. И есть рюкзак, определенной вместимости. Задача заключается в том, чтобы собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом весовое ограничение рюкзака.
2. Задача «Банкомат»
В банкомате имеется банкноты n различных номиналов a1, a2, …, an.
Клиент хочет получить сумму в K денежных единиц.
Необходимо определить, при помощи какого минимального числа банкнот можно выдать эту сумму (а при необходимости восстановления
ответа - определить способ выдачи, использующий минимальное число банкнот).
Очевидно приходящий в голову «жадный алгоритм» - выдавать банкноты наиболее крупного номинала, пока это возможно, затем переходить
к более мелкому номиналу, в общем случае неверен.
Например, пусть номиналы банкнот a1 = 1, a2 = 50, a3 = 90, а сумма для выдачи K = 100.
Тогда «жадный» алгоритм выдаст банкноту в 90 и 10 банкнот по 1, в то время как существует решение, использующее всего лишь две
банкноты по 50.
На помощь придет динамическое программирование.
Пусть F(k) - минимальное число банкнот, при помощи которых можно выдать сумму в k рублей.
Выберем одну из банкнот, входящую в оптимальный способ выдачи.
Пусть это банкнота ai. Тогда необходимо выдать оставшуюся сумму k − ai, что можно сделать при помощи F(k − ai) банкнот.
То есть F(k) = 1 + F(k−ai).
Далее необходимо взять минимум по всем возможным значениями i: F(k) = 1 + miniF(k − ai).
Начальные значения удобно сделать такими: F(0) = 0, F(k) = +∞ при k < 0.
Значение +∞ будет означать невозможность выдачи суммы вообще, то есть «очень плохой вариант», когда банкнот потребуется бесконечно много.
Можно добавить к списку значений функции F(k) «каемочку» для отрицательных значений k, но лучше просто рассматривать только такие
значения k и i, когда k − ai ≥ 0.
В данном примере программы будем считать, что номиналы банкнот хранятся в спискe A и нумерация банкнот начинается с числа 0.
INF = 10 ** 10
F = [INF] * (K + 1)
F[0] = 0
for k in range(1, K + 1):
for i in range(len(A)):
if k - A[i] >= 0 and F[k - A[i]] < F[k]:
F[k] = F[k - A[i]]
F[k] += 1
Для восстановления ответа будем опять идти «к началу» списка, уменьшая сумму k, выбирая такую банкноту ai, что F(k) = F(k − ai) + 1.
Номиналы банкнот, которые будут при этом использоваться для восстановления ответа, будут записаны в список Ans.
Ans = []
k = K
while k != 0:
for i in range(len(A)):
if k - A[i] >= 0 and F[k] == F[k - A[i]] + 1:
Ans.append(A[i])
k -= A[i]
3. Задача «Золотые слитки»
Предыдущий алгоритм также решал задачу проверки возможности выдачи любой суммы при помощи заданного номинала банкнот - сумму k
возможно выдать, если F(k) < +∞.
Также в предыдущей задаче банкнот каждого номинала было неограниченно много.
Теперь рассмотрим задачу, в которой существует ровно одна банкнота каждого номинала (но номиналы банкнот могут повторяться),
необходимо проверить, можно ли заданную сумму K выдать при помощи данных банкнот.
Этой задаче можно придать и такой смысл: есть n золотых слитков массами a1, a2, …, an.
Какую максимальную массу золота можно унести, если она не может превышать K (то есть «грузоподъемность» не превосходит K).
Задачу также можно решать при помощи динамического программирования.
Пусть F(k) - признак того, можно ли набрать слитков на массу в точности k, то есть одно из двух значений True (или 1) или False (или 0).
Будем по очереди рассматривать все слитки, обновляя значения F(k).
При рассмотрении слитка ai необходимо пометить F(k) = 1, если F(k − ai) = 1, то есть если массу в точности k можно набрать,
если ранее было возможно набрать массу в точности k − ai.
F = [0] * (K + 1)
F[0] = 1
for i in range(len(A)):
F_new = F[:] # копия списка F для обновления
for k in range(A[i], K + 1):
if F[k - A[i]] == 1:
F_new[k] = 1
F = F_new
Данный алгоритм нуждается в пояснении.
В самом начале список F заполняется значением 0, кроме F(0) = 1, что означает, что нулевую массу можно набрать не используя
ни одного слитка, а любую другую массу не используя ни одного слитка, набрать нельзя.
Внутренний цикл начинается со значения ai, так как массу k можно набрать, если ранее было возможно набрать массу k − ai,
то есть минимальное значение для k равно ai.
Кроме того, нельзя вносить исправления сразу же в список F, потому что в этом случае один предмет будет учтен более одного раза,
то есть будут помечены единицами F(ai), затем - F(2ai), так как F(ai)=1, затем F(3ai) и т. д.
Чтобы избежать этой ошибки, в этом алгоритме создается копия списка F и в него вносятся изменения,
тем самым не будут учитываться изменения в списке, сделанные при добавлении слитка ai.
Другой способ избежать этой проблемы - обходить список F с конца - от большего значения к меньшему.
F = [0] * (K + 1)
F[0] = 1
for i in range(len(A)):
for k in range(K, A[i] - 1, -1):
if F[k - A[i]] == 1:
F[k] = 1
Для восстановления ответа для каждого значения k будем хранить массу слитка, при помощи которого он был получен, будем хранить
его в списке Prev.
Значение списка Prev будет обновляться при записи F(k) = 1:
F = [0] * (K + 1)
F[0] = 1
Prev = [0] * (K + 1)
for i in range(len(A)):
for k in range(K, A[i] - 1, -1):
if F[k - A[i]] == 1:
F[k] = 1
Prev[k] = A[i]
Теперь для восстановления ответа будем уменьшать значение k на Prev(k) пока не получим k = 0.
Ans = []
k = K
while k > 0:
Ans.append(Prev[k])
k -= Prev[k]
4. Дискретная задача об укладке рюкзака.
Следующим обобщением задачи про золотые слитки является «задача об укладке рюкзака».
В этой задаче также имеется несколько предметов, для каждого предмета заданы две характеристики: вес 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 будут храниться номера предметов, входящих в рюкзак.