калькулятор изменений (номиналов)

Question

Я ищу решение для расчета номиналов изменений.Моя проблема имеет номиналы: 50 и 20.

Итак, учитывая количество: 130, должно быть 1x50 + 4x20, а количество: 80, должно быть 0x50 + 4x20 и т. Д.

Я попытался найти проблему с монетами, но не смог найти достойного ответа, и, когда существует более двух типов наименований, кажется, что для проблемы с монетами существует кирпичная стена (из того, что я прочитал).

Есть ли полное решение для этого?Или, предпочтительно, решение для более чем двух типов номиналов?

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

Бонус, если вы можете решить в псевдокоде

Answer 1

Если у вас есть только два наименования, проблема становится:

find x and y such that 
a*x + b*y = c

Эту проблему можно решить с помощью расширенного евклидова алгоритма

---

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

Answer 2

вы можете использовать простой «жадный алгоритм»

http://en.wikipedia.org/wiki/Greedy_algorithm

Answer 3

Вот кодовое решение: http://www.codeproject.com/KB/recipes/coinChangeProblem.aspx

к сожалению, код действительно ужасен, но его можно легко очистить

Answer 4

Отметьте относительный, но более общий вопрос ищите, чтобы понять, чем объясняется ценность денег на math.stackexchange.com.

Также делает-проблемы изменения количества долларов * и других числовых разделов , которые хорошо объясняют, как генерирующие функции являются решением общей проблемы.

Если ваша задача ограничена двумя монетами,это намного проще.

Answer 5

Просто продолжайте вычитать самую большую деноминацию, какую только сможете. То есть продолжайте вычитать 50 с до тех пор, пока оставшееся число не станет <50, затем продолжайте вычитать 20 с Это работает независимо от того, сколько у вас деноминаций. </p>