Учитывая набор монет с различными конфессиями и значение v, вы хотите найти наименьшее количество монет, необходимое для представления значения v.
Например, для набора монет 1,5,10,20 это дает 2 монеты на сумму 6 и 6 монет на сумму 19.
Мой главный вопрос: когда можно использовать жадную стратегию для решения этой проблемы?
Бонусные баллы: действительно ли это утверждение неверно? (От: Как определить, достаточно ли жадного алгоритма для задачи минимальной замены монет? )
Тем не менее, в этой статье есть доказательство того, что если жадный алгоритм работает для первого наибольшего значения denom и второго по величине значения denom, то он работает для всех них и предлагает просто использовать жадный алгоритм против оптимального алгоритма DP для его проверки. http://www.cs.cornell.edu/~kozen/papers/change.pdf
Ps. обратите внимание, что ответы в этой теме невероятно грубые, поэтому я задал вопрос заново.
источник
Ответы:
Система монет является канонической, если количество монет, приведенных в замене алгоритмом жадности, является оптимальным для всех сумм.
Статья Д. Пирсона. Алгоритм полиномиального времени для задачи изменения. Операции Исследования Письма, 33 (3): 231-234, 2005 предлагает алгоритм для решения, является ли система монет канонической, где n - количество монет различных типов. Из аннотации:O ( n3) N
Бумага довольно короткая.
В этом семматическом вопросе также есть некоторые обсуждения .
источник
canonical coin system
. Было бы здорово, если бы вы могли добавить пример, то есть, как проверить предложенную систему1,5,10,20