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

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

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

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

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

Подсчет кол-ва нулевых подмассивов

Март 21, 2023 г.

Разбор задачи с литкода. (2348. Number of Zero-Filled Subarrays). Суть: есть массив чисел, нужно подсчитать кол-во подмассивов, состоящих из нулей. Например, дан массив [0, 0, 1]. Как видим, есть последовательность из двух нулей в начале ...

Читать

87. Scramble string - задача о перетасованных строках

Март 30, 2023 г.

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

Читать

 

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

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



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