с изменениями с изменениями

Question

В задаче изменения со следующими алгоритмами Greedy обращается к следующему вопросу: как можно сделать заданную сумму денег с наименьшим количеством монет?

Алгоритм: использование наиболее ценных монет, если возможно. Предположим, что у нас есть бесконечное число каждого набора монет.

Мой профессор, написал (4), не дает оптимального решения, кто мог бы сказать, почему? (Или почему другие не контрпример?)

1- {1,2,5} 

2- {1,4,7} 

3-{1,5,10} 

4-{1,7,10} 

Answer 1

Применяя жадный стратегию с монетами из набора № 4 не будет производить оптимальный результат в ситуации, когда необходимо представить 14:

• Жадные стратегии будет принимать 10, как только это возможно, заканчивая четырьмя пенни, в общей сложности пять монет
• Оптимальной стратегией было бы взять две семерки, в общей сложности две монеты.

Легко видеть, что если существует монета C, что значение k*C может состоять, по крайней мере k+1 монет, если вы принимаете какие-либо из монет высшего номинала, то жадный алгоритм не собирается добиться успеха.

В вашем последнем комплекте C=7, k=2, kC=14. Если вы возьмете 10, чтобы сделать 14, вам понадобятся пять монет, которые больше k.