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]