Задача о размене монет

Кассир, выдающий сдачу, берет самую крупную подходящую монету, потом следующую, и для евро или долларов это всегда дает наименьшее число монет. Но замените монеты на 1, 3 и 4, и та же привычка заплатит 6 тремя монетами, хотя хватило бы двух. Динамическое программирование находит настоящий минимум для любых монет.

Ряд сумм, у каждой — наименьший набор монет, который ее составляет, над монетами трех разных размеров
Ряд сумм, у каждой — наименьший набор монет, который ее составляет, над монетами трех разных размеров

Два вопроса

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

Минимум монет шаг за шагом

Сделайте ряд клеток для сумм от 0 до целевой. Для суммы 0 нужно 0 монет; каждая другая сумма начинается с бесконечности. Идите по суммам по порядку и для каждой пробуйте каждую подходящую монету c: клетка для суммы минус c плюс одна монета — это кандидат. Оставляйте наименьший. Каждая клетка зависит только от клеток слева, которые уже окончательны, поэтому один проход заполняет весь ряд.

Пример

С монетами 1, 3 и 4: для суммы 1 нужна 1 монета, для 2 — 2, для 3 — 1 (одна монета 3), для 4 — 1. Для 5 пробуем 1 (для 4 нужна 1, итого 2 монеты), 3 (для 2 нужно 2, итого 3 монеты) и 4 (для 1 нужна 1, итого 2 монеты): лучшее — 2. Для 6 пробуем 1 (для 5 нужно 2, итого 3), 3 (для 3 нужна 1, итого 2) и 4 (для 2 нужно 2, итого 3): лучшее — 2, как 3 + 3. Жадный метод заплатил бы 4 + 1 + 1.

Подсчет способов

Чтобы считать сочетания, добавляйте монеты по одной. Когда есть только первая монета, каждую сумму можно составить одним способом или никак. Когда добавляется новая монета c, способы составить сумму a — это прежние способы без c плюс способы составить a − c, где c снова разрешена, потому что каждый из них, если добавить еще одну c, становится способом составить a. С монетами 1, 2 и 5 сумму 5 можно составить 4 способами: 5, 2 + 2 + 1, 2 + 1 + 1 + 1 и 1 + 1 + 1 + 1 + 1.

Когда хватает жадного метода

Систему монет, для которой жадный метод всегда дает наименьшее число монет, называют канонической. Большинство современных валют устроены именно так, а в 1994 году Дэвид Пирсон описал проверку системы монет за число шагов, которое растет лишь полиномиально с числом монет. Старые британские монеты не были каноническими: жадный метод платит 48 пенсов полкроной, шиллингом и шестипенсовиком, хотя хватило бы двух флоринов.

Попробуйте сами

Откройте приложение, перейдите в вид «Таблица» и нажмите Шаг. В режиме Минимум монет оранжевая клетка — вычисляемая сумма, а синяя — меньшая сумма, которая остается после монеты; строка под ними хранит последнюю монету, и в конце монеты считываются обратно по ней. Переключитесь на Число способов и смотрите, как значения растут строка за строкой по мере добавления монет.

Часто задаваемые вопросы

Задача о размене монет — это задача о рюкзаке?

Близкая родственница. Вариант с минимумом монет — это задача о неограниченном рюкзаке, в которой каждая монета — предмет с весом, равным ее номиналу, рюкзак нужно заполнить точно, а цель — наименьшее число предметов.

Какова временная сложность?

O(k·A) для k видов монет и суммы A в обоих вариантах. Таблица для минимума монет содержит A + 1 клеток, а таблица для способов — (k + 1)·(A + 1), хотя достаточно одной строки, если обновлять клетки на месте.

Зачем считать монеты в фиксированном порядке?

Если бы каждая сумма пробовала каждую монету, 1 + 2 и 2 + 1 считались бы двумя способами. Когда монеты добавляются по одной строке за раз, сочетание всегда строится сначала из более ранних монет, поэтому каждое считается ровно один раз.

Можно ли восстановить монеты для числа способов?

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

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Попробовать размен монет