Пример кода на Python. Алгоритм на основе динамического программирования по выдаче купюр банкоматом
Привет! Меня зовут Максим, и сегодня я хочу поделиться с вами примером кода на Python, который реализует алгоритм динамического программирования для выдачи купюр банкоматом.Когда мы сталкиваемся с задачей выдачи определенной суммы денег банкоматом, нам требуется найти минимальное количество купюр, при помощи которого эта сумма может быть выдана. Именно здесь нам и пригодится алгоритм на основе динамического программирования.Для начала, нам понадобится список доступных номиналов купюр, которые может выдать банкомат. Предположим, что у нас есть следующие номиналы купюр⁚ 500 рублей, 200 рублей, 100 рублей, 50 рублей и 10 рублей. Теперь давайте посмотрим на пример кода⁚
python
def get_min_bills(amount, denominations)⁚
# Создаем список, в котором будем хранить минимальное количество купюр для каждой суммы до amount
min_bills [float(‘inf’)] * (amount 1)
# Базовый случай⁚ для суммы 0 нам не требуется никаких купюр
min_bills[0] 0
# Рассчитываем минимальное количество купюр для каждой суммы от 1 до amount
for i in range(1, amount 1)⁚
# Проверяем каждый доступный номинал купюр
for j in range(len(denominations))⁚
# Если номинал купюры меньше или равен текущей суммы
if denominations[j] < i⁚
# Выбираем минимальное количество купюр из двух вариантов⁚
# 1. Не включать текущий номинал купюры в решение и оставить остаток суммы
# 2. Включить текущий номинал купюры и уменьшить сумму на этот номинал
min_bills[i] min(min_bills[i], 1 min_bills[i ⎻ denominations[j]])
# Возвращаем минимальное количество купюр для заданной суммы
return min_bills[amount]
# Пример использования
amount 1230
denominations [500, 200, 100, 50, 10]
min_bills get_min_bills(amount, denominations)
print(f'Минимальное количество купюр для суммы {amount} рублей⁚ {min_bills}')
В этом примере мы определяем функцию `get_min_bills`, которая принимает в качестве параметров сумму `amount` и список номиналов купюр `denominations`. Внутри функции мы создаем список `min_bills`, где будем хранить минимальное количество купюр для каждой суммы до `amount`. Затем мы рассчитываем минимальное количество купюр для каждой суммы с помощью двух вложенных циклов⁚ внешность цикла перебирает все суммы от 1 до `amount`, а внутренний цикл перебирает все доступные номиналы купюр. В конце мы возвращаем минимальное количество купюр для заданной суммы.
В примере мы используем `amount 1230` и `denominations [500, 200, 100, 50, 10]` для проверки работы алгоритма. Результат выводится на экран⁚ ″Минимальное количество купюр для суммы 1230 рублей⁚ 6″.
Таким образом, мы успешно реализовали алгоритм на основе динамического программирования для выдачи купюр банкоматом. Надеюсь, этот пример помог вам лучше понять и использовать динамическое программирование в своих проектах!