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

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

Также в задаче (литкод №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 для мемоизации, но принципиально алгоритм от этого не поменяется.

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

Задача: подсчета кол-ва возможных маршрутов

Июнь 25, 2023 г.

Решаем задачу с литкода №1575 Count All Possible Routes. Дан массив чисел, описывающий города. Указаны индексы стартового города (start) и города, куда нужно приехать (finish), а также запас топлива (fuel). Требуется найти кол-во путей, по которым ...

Читать

Задача группировки подобных строк

Апрель 28, 2023 г.

Речь идет о № 839 с leetcode. Формулируется проблема таким образом - дан массив строк, которые отличаются (или не отличаются) друг от друга перестановкой ...

Читать

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

Июнь 3, 2023 г.

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

Читать

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

Март 15, 2023 г.

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

Читать
 

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

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



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