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

В этом параграфе вы познакомитесь с одной из самых известных жадных задач — разменом денег. Нужно уметь разложить сумму по монетам так, чтобы их количество оказалось минимальным. На первый взгляд достаточно всегда брать наибольший подходящий номинал, но такой метод работает не для любых наборов монет. Поэтому важно понять, в каких случаях жадная стратегия действительно гарантирует оптимальный результат. Этот подход ляжет в основу всех задач этой главы.

Ключевые вопросы параграфа

• Как работает жадный алгоритм в задаче про размен монет и чем он отличается от полного перебора?
• Почему важно обосновывать правильность жадных решений и как это сделать?

Простой жадный алгоритм

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

Предположим, что у кассира есть бесконечное количество монет всех номиналов.

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

Пример 1

• .

Пример 2

• .

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

• Ограничение по памяти: 512 Mb.

Решение

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

1Change(money):
2    numCoins = 0
3    while money>0:
4        if money >= 10:
5            money = money − 10
6        else if money >= 5:
7            money = money − 5
8        else:
9            money = money − 1
10        numCoins = numCoins + 1
11    return numCoins

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

1return 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 — , но его однострочная версия требует лишь несколько арифметических операций.

Что дальше

Теперь вы знаете, как устроена жадная стратегия и как она работает в задаче размена. Вы увидели, что можно принимать решения, не заглядывая вперёд, — и при этом получить оптимальный результат. А ещё убедились, что даже простая стратегия требует проверки и не всегда даёт правильный ответ.

Далее — новая задача: как выбрать самые ценные предметы, если ресурсы ограничены. Здесь используется жадный отбор по плотности: ценность на единицу веса или объёма. Вы познакомитесь с жадным отбором по плотности и научитесь использовать этот подход, когда важно получить максимум от доступного.

А пока вы не ушли дальше — закрепите материал на практике:

• Отметьте, что урок прочитан, при помощи кнопки ниже.
• Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.
• Перейдите к задачам этого параграфа и потренируйтесь.
• Перед этим — загляните в короткий гайд о том, как работает система проверки.

Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.

Ключевые выводы параграфа

• Жадный алгоритм принимает решение на каждом шаге, выбирая наиболее выгодный вариант здесь и сейчас.
• В задаче размена такая стратегия работает, если номиналы монет удовлетворяют определённым условиям.
• Даже для простых на вид задач важно доказывать корректность жадного подхода, а не полагаться на интуицию.
• Жадные алгоритмы просты и быстры, но требуют проверки: в некоторых задачах они могут давать неверный результат.