Проблема состоит в том, чтобы разменять n центов на четверти, десять центов, пятак и пенни, используя наименьшее общее количество монет. В частном случае, когда четыре номинала - четвертинки, десять центов, никель и пенни, мы имеем c1 = 25, c2 = 10, c3 = 5 и c4 = 1.
Если у нас есть только четверти, десять центов и пенни (и ни один пятак), жадный алгоритм внесет изменения в 30 центов, используя шесть монет - четверть и пять пенни. - тогда как мы могли использовать три монеты, а именно три цента.
Учитывая набор номиналов, как мы можем сказать, создает ли жадный подход оптимальное решение?
