6.1. Задача «Размен»

Давайте реализуем простой жадный алгоритм, которым пользуются кассиры по всему миру. Предположим, что у кассира есть бесконечное количество монет всех номиналов.

• Входные данные: Целое число .
• Выходные данные: Минимальное количество монет номиналами , , , чтобы выдать сдачу .
• Ограничения: .

Пример 1

Ввод	Вывод
2	2

• .

Пример 2

Ввод	Вывод
28	6

• Ограничение по времени (с): 1 секунда.
• Ограничение по памяти: 512 Mb.

Решение

Рассмотрим основную идею решения. Пока сдача положительна , мы выбираем монету с самым большим номиналом, не превышающем , отнимаем значение номинала выбранной монеты от и увеличиваем количество монет:

Change(money):
    numCoins = 0
    while money>0:
        if money >= 10:
            money = money − 10
        else if money >= 5:
            money = money − 5
        else:
            money = money − 1
        numCoins = numCoins + 1
    return numCoins

Также эту задачу можно решить в одну строку:

return floor(money/10) + floor((money mod 10)/5) + (money mod 5)

Проектировать жадные алгоритмы просто, но вот доказывать их правильность — нередко сложная задача. И возможно, вас интересует, почему мы тратим время, чтобы доказать работоспособность очевидного алгоритма Change. Дождитесь, пока мы попадем в алгоритмическую ловушку, и она убедит вас, что доказательство ниже — не трата времени.

Чтобы доказать, что этот жадный алгоритм работает правильно, мы покажем, что выбор монеты с самым большим номиналом соответствует некому оптимальному решению.

То есть нам нужно доказать, что для каждого положительного целого числа существует оптимальный способ выдать сдачу с , который использует как минимум одну монету с номиналом , где — самое большое число из , не превышающее . Чтобы доказать это, мы рассмотрим несколько примеров. В каждом из примеров мы выбираем оптимальное решение (то есть конкретную сдачу с ) и преобразовываем его так, что количество монет не увеличивается и содержит как минимум одну монету с номиналом . Мы также получаем способ выдать сдачу с , который содержит монету , если начинаем с подхода к сдаче .

• . В этом случае , и единственный способ выдать сдачу с — это использовать монет номиналом 1.
• . В таком случае . Безусловно, любая сдача с money будет состоять только из монет с номиналами 1 и 5. Если в неё не входит монета с номиналом 5, то входят как минимум пять монет номиналом 1 (так как ). Заменив их на одну монету номиналом 5, мы улучшим это решение.
• . В таком случае . Рассмотрим способ выдать сдачу с и предположим, что в нём не используется монета номиналом 10. Простое, но важное замечание: сумма некой подгруппы использованных монет — 10. Это можно продемонстрировать, рассмотрев количество монет номиналом 5 в данном решении: если таких монет нет, тогда есть как минимум десять монет номиналом 1, и мы заменяем их на одну 10; если есть лишь одна монета номиналом 5, тогда есть как минимум пять монет по 1, и мы снова заменяем все монеты на одну монету номиналом 10; если есть хотя бы две монеты по 5, тогда их снова можно заменить.

Хотя это доказательство длинное и довольно скучное, каждый раз, когда вы придумываете жадный алгоритм, вам нужно доказательство! Следующее упражнение показывает более компактный способ доказать правильность алгоритма выше.

✒️ Упражнение:
Продемонстрируйте, что money mod 5 монет номиналом 1 необходимы для любого решения, а остальные следует заменить монетами номиналами 10 и максимум одной монетой номиналом 5.

Время выполнения. Время выполнения алгоритма Change — , но его однострочная версия требует лишь несколько арифметических операций.