Задача: подсчитать варианты размена монет

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

Также в задаче (литкод №518) сказано, что сумма не превышает 5000, а кол-во номиналов для размена не превышает 300.

Брут форс

Допустим, что у нас есть набор монет [1, 2, 5], и нужно найти размен для 5.

Шаг 0. Представим, что мы отслеживаем разменные наборы. В начале у нас есть только один набор, где нет монет — запишем его как [0, 0, 0].

Шаг 1. На следующем шаге добавляем к набору поочередно одну из монет. Так мы получим три новых набора — [1, 0, 0] (сумма 1), [0, 1, 0] (сумма 2) и [0, 0, 1] (сумма 5).

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

Так у нас останется два набора. С ними вернемся на шаг №1. И будем повторять эти операции, пока у нас есть наборы монет.

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

Вот реализация этого алгоритма (TypeScript):

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

Динамическое программирование

Задача является классическим примером задач на динамическое программирование.

В чем заключается данный подход? Нам требуется ввести индукцию (рекурсию). Т.е. нужно найти решение проблемы через решение более простых случаев.

Рассмотрим ту же задачу — есть монеты [1, 2, 5], нужно найти все способы разменять 5.

Шаг 0. У нас есть полный набор для размена и полная сумма = 5

Шаг 1. Перед нами выбор — использовать первую монету из набора монет для размена или нет. Т.е. задача распадается на две подзадачи

  • с использованием текущей монеты, но суммой уменьшенной на номинал монеты;
  • без использования текущей монеты (убираем её из набора), но с прежней суммой.

Если сумма равна нулю, то вернем 1 — мы нашли верную комбинацию. Если сумма отрицательная или мы отказались уже от всех монет, то вернем 0.

Решая подзадачи мы снова возвращаемся к шагу 1. Но при этом у нас либо меньше сумма, либо в наборе осталось меньше монет.

Посмотрим реализацию.

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

Тут более оптимально использовать массив вместо Map для мемоизации, но принципиально алгоритм от этого не поменяется.

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

TS: функция преобразования к каноническому пути

Март 15, 2023 г.

Увидел эту задачу на leetcode - https://leetcode.com/problems/simplify-path/, где не так часто встречаются задачи близкие к практиктическому программированию. Ранее уже приводил решение подобной задачи для PHP. Здесь порешаем её уже на TS. Задача ...

Читать

Задача следующей комбинации (next permutation)

Март 13, 2023 г.

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

Читать

Результат k-ой перестановки

Июль 5, 2023 г.

Очередная задача с литкода (№60. Permutation Sequence). В общем случае формулируется так: дан набор элементов, требуется вернуть этот набор после k перестановок. ...

Читать

Задача о поиске всех подходящих под-сум

Июль 1, 2023 г.

№560 leetcode Subarray Sum Equals K. Есть массив чисел, и дано значение k. Надо найти все последовательные под-массивы сумма которых равна k. В условиях также сказано, что числа в массиве могут быть как положительные, так и отрицательные. Если ...

Читать
 

Комментарии к «Задача: подсчитать варианты размена монет»

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



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