Классическая задача о размене монет

Дана сумма amount и номиналы монет. Требуется разменять сумму минимальным набором монет.

Если рассматривать набор монет, который используется в реальной жизни, т.е. [1коп, 5коп, 10коп, 50коп, 1р, 2р, 5р, 10р], то во-первых, решение всегда существует, т.к. мы может взять всю сумму по 1 копейке, а во-вторых, можно применить быстро сходящийся, т.н. «жадный алгоритм».

Жадный алгоритм

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

Реализация на JS(TS):

Такой алгоритм не даст желаемого результата (т.е. минимального числа монет) или вообще не найдет решения для произвольного набора монет. Область его применимости ограничивается набором монет, где каждый следующий номинал кратен предыдущему или составлен из суммы двух предыдущих номиналов (50 коп = 10 коп x5, а 5р = 2р * 2 + 1р).

Например, для [7, 8] и суммы 30, функция выдаст -1, хотя довольно очевидно, что можно взять две монеты по 8 и две монеты по 7, чтобы разменять требуемую сумму.

Рекурсия

Старая добрая рекурсия или динамический алгоритм.

Возьмем другой пример — набор монет [1, 4, 6] и сумма 8. Жадный алгоритм выдаст нам результат 3 — 6×1, 1×2, хотя более оптимально взять 2 монеты номиналом 4.

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

Логика в рекурсии будет следующая: на каждом шаге вы стоите перед выбором — начать пользоваться монетами другого номинала или использовать одну монету выбранного номинала.

Нас интересует минимум монет, потому мы сравним оба результата и оставляем тот, что требует меньше монет.

Давайте рассмотрим пример реализации. Я написал его на JS/TS и мне было интересно выводить не только общее кол-во монет, но и кол-во каждой из монет

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

Зато можно получить размен для таких экзотических случаев как [55, 56, 57] и 1000:

Проблему быстродействия можно попробовать решить, применяя гибридный алгоритм.

Гибридный алгоритм

Он также использует рекурсивные вычисления, но в форме накопления итога. Я не стал его загромождать подсчетом номинала отдельных монет и оптимизировать, чтобы более внятно пояснить суть.

Для нахождения минимально требуемого кол-ва монет, мы строим таблицу. Каждая строка соответствует своему номиналу монет, а по столбцам у нас разворачивается весь диапазон суммы размена [0 … amount].

Т.е. таблица, как вы понимаете, очень большая. Тем не менее, размер amount и набор номиналов тут могут быть гораздо больше, чем в рекурсивной реализации, а сложность вычислений будет расти лишь линейно.

Что же мы вычисляем в этой большой матрице? Рассмотрим кейс [3, 8, 9] и сумму 16.

012345671516
30
80
90

Логика следующая — мы начинаем с наименьшей монеты (индекс j) и идем вдоль строки таблицы увеличивая сумму (индекс i). Каждый раз мы вычисляем (если это возможно), сколько монет требуется чтобы разменять сумму i.

012345671516
30125
80
90

Вычисляется каждая ячейка так: берем минимум двух значений — 1) результат из строки j-1 (если она есть), и 2) — значение для того же номинала, но для [j][i — [номинал монеты]] + 1.

Для монеты 3 предыдущей строки нет, потому мы имеем только кратные трем значения в соответствующих столбцах. Технически, значение для [i][3] получено как = i[0] + 1, а не просто i % 3.

Для 8ки, к примеру, [j][14], получается так — значения на предыдущей строке нет, а на текущей составляет [j][14-8] + 1, туда попала двойка из предыдущей строки. Мы как бы к двум монетам по 3 добавили монету на 8, и так разложили 14.

01236789141516
301235
801213352
90

Так возникает рекурсивная связь между строками и, так как мы выбираем каждый раз минимум из двух пар значений, то получаем каждый раз оптимальное кол-во монет для размена суммы i.

Конечным результатом становится значение в правом нижнем углу таблицы.

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

Написать комментарий

Мало букафф? Читайте есчо !

Поиск самой длинной петли в графе

Март 26, 2023 г.

Как говорили учителя в школе - а теперь для самых умных задача со звездочкой. "Longest cycle in a graph" отмечена как сложная задача на leetcode. Давайте разберем как её решить. Дан массив, который описывает ориентированный граф. В каждой ячейке ...

Читать

Поиск выхода из лабиринта

Июнь 3, 2023 г.

Продолжаем разбор классических задач по программированию. На этот раз лабиринтовая задача, которая формулируется так - дан плоский лабиринт в виде двумерного массива, где стенка отмечена 1, а свободный участок как 0. Также дана начальная позиция игрока, ...

Читать

 

Комментарии к «Классическая задача о размене монет»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: