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]