Когда жадный алгоритм может решить проблему смены монет?

24

Учитывая набор монет с различными конфессиями и значение v, вы хотите найти наименьшее количество монет, необходимое для представления значения v.с1,,,,,сN

Например, для набора монет 1,5,10,20 это дает 2 монеты на сумму 6 и 6 монет на сумму 19.

Мой главный вопрос: когда можно использовать жадную стратегию для решения этой проблемы?


Бонусные баллы: действительно ли это утверждение неверно? (От: Как определить, достаточно ли жадного алгоритма для задачи минимальной замены монет? )

Тем не менее, в этой статье есть доказательство того, что если жадный алгоритм работает для первого наибольшего значения denom и второго по величине значения denom, то он работает для всех них и предлагает просто использовать жадный алгоритм против оптимального алгоритма DP для его проверки. http://www.cs.cornell.edu/~kozen/papers/change.pdf

Ps. обратите внимание, что ответы в этой теме невероятно грубые, поэтому я задал вопрос заново.

Несчастный кот
источник
Для бинарной задачи о ранце существует легко формулируемый критерий: жадный алгоритм решает задачу, если для всех номиналов . Не так просто для замены монет (рюкзак с произвольными интегральными переменными). Вам нужна экспозиция Журнала, Немхаузера и Троттера? ся>ΣJзнак равно1я-1сJ
Дмитрий Чубаров
2
В заявлении Декстера Козена говорится, что если жадный алгоритм согласуется с оптимальным для всех , то он даст оптимальное решение для произвольного v . Я не вижу ничего плохого в этом утверждении. v<сN-1+сNv
Дмитрий Чубаров
@ Дмитрий Чубаров Спасибо, теперь я понимаю, как работает бонус q. Это сродни сильной индукции? Что касается вашего другого вопроса, я хотел бы получить ответ, который дает решение и предпочтительно доказательство.
Несчастный кот
Я подниму вопрос, и если никто не встанет, подытожим MNT с несколькими примерами за выходные.
Дмитрий Чубаров
Смотрите также этот связанный вопрос ; в частности, интересная статья Шаллита может представлять интерес.
Рафаэль

Ответы:

13

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

Статья Д. Пирсона. Алгоритм полиномиального времени для задачи изменения. Операции Исследования Письма, 33 (3): 231-234, 2005 предлагает алгоритм для решения, является ли система монет канонической, где n - количество монет различных типов. Из аннотации:О(N3)N

Затем мы получаем набор из возможных значений, которые должны содержать наименьший контрпример. Каждый из них может быть проверен с помощью O ( n ) арифметических операций, что дает нам алгоритм O ( n 3 ) .О(N2)О(N)О(N3)

Бумага довольно короткая.

сс

О(N2)N

В этом семматическом вопросе также есть некоторые обсуждения .

Марк Доминус
источник
Спасибо. Я вижу, что вопрос гораздо более сложный, чем я думал - наверное, поэтому вы не опубликовали фактические критерии? Моя идея о том, что «если все монеты кратны друг другу, жадный алгоритм дает оптимальный результат», очевидно, была слишком простой.
Несчастный Кот
Я не опубликовал фактические критерии, потому что я не запомнил наизусть и у меня не было времени перечитать статью. Вы, конечно, можете смело редактировать мой ответ.
Марк Доминус
Я прочитал ответ и статью пару раз, но я не смог найти понятные человеку критерии canonical coin system. Было бы здорово, если бы вы могли добавить пример, то есть, как проверить предложенную систему1,5,10,20
Крестный отец