Давайте реализуем простой жадный алгоритм, которым пользуются кассиры по всему миру. Предположим, что у кассира есть бесконечное количество монет всех номиналов.
- Входные данные: Целое число $money$.
- Выходные данные: Минимальное количество монет номиналами $1$, $5$, $10$, чтобы выдать сдачу $money$.
- Ограничения: $1 \le money \le 10^3$.
Пример 1
Ввод | Вывод |
---|---|
2 | 2 |
- $2=1+1$.
Пример 2
Ввод | Вывод |
---|---|
28 | 6 |
$28=10+10+5+1+1+1$.
Ограничение по времени (с): 1 секунда.
Ограничение по памяти: 512 Mb.
Решение
Рассмотрим основную идею решения. Пока сдача положительна $money>0$, мы выбираем монету с самым большим номиналом, не превышающем $money$, отнимаем значение номинала выбранной монеты от $money$ и увеличиваем количество монет:
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
. Дождитесь, пока мы попадем в алгоритмическую ловушку, и она убедит вас, что доказательство ниже — не трата времени.
Чтобы доказать, что этот жадный алгоритм работает правильно, мы покажем, что выбор монеты с самым большим номиналом соответствует некому оптимальному решению.
То есть нам нужно доказать, что для каждого положительного целого числа $money$ существует оптимальный способ выдать сдачу с $money$, который использует как минимум одну монету с номиналом $D$, где $D$ — самое большое число из $1,5,10$, не превышающее $money$. Чтобы доказать это, мы рассмотрим несколько примеров. В каждом из примеров мы выбираем оптимальное решение (то есть конкретную сдачу с $money$) и преобразовываем его так, что количество монет не увеличивается и содержит как минимум одну монету с номиналом $D$. Мы также получаем $оптимальный$ способ выдать сдачу с $money$, который содержит монету $D$, если начинаем с $оптимального$ подхода к сдаче $money$.
- $1 \le money \lt 5$. В этом случае $D=1$, и единственный способ выдать сдачу с $money$ — это использовать $money$ монет номиналом 1.
- $5 \le money \lt 10$. В таком случае $D=5$. Безусловно, любая сдача с money будет состоять только из монет с номиналами 1 и 5. Если в неё не входит монета с номиналом 5, то входят как минимум пять монет номиналом 1 (так как $money \ge 5$). Заменив их на одну монету номиналом 5, мы улучшим это решение.
- $10 \le money$. В таком случае $D=10$. Рассмотрим способ выдать сдачу с $money$ и предположим, что в нём не используется монета номиналом 10. Простое, но важное замечание: сумма некой подгруппы использованных монет — 10. Это можно продемонстрировать, рассмотрев количество монет номиналом 5 в данном решении: если таких монет нет, тогда есть как минимум десять монет номиналом 1, и мы заменяем их на одну 10; если есть лишь одна монета номиналом 5, тогда есть как минимум пять монет по 1, и мы снова заменяем все монеты на одну монету номиналом 10; если есть хотя бы две монеты по 5, тогда их снова можно заменить.
Хотя это доказательство длинное и довольно скучное, каждый раз, когда вы придумываете жадный алгоритм, вам нужно доказательство! Следующее упражнение показывает более компактный способ доказать правильность алгоритма выше.
✒️ Упражнение:
Продемонстрируйте, что money mod 5 монет номиналом 1 необходимы для любого решения, а остальные следует заменить монетами номиналами 10 и максимум одной монетой номиналом 5.
Время выполнения. Время выполнения алгоритма Change
— $O(money)$, но его однострочная версия требует лишь несколько арифметических операций.