Жадный алгоритм внесения изменений - это алгоритм, который вносит изменения, выбирая наибольшую номинальную стоимость монеты из доступных, пока не достигнет количества изменений, которые пытается внести.Удивительно, но этот алгоритм на самом деле работает для внесения изменений наиболее эффективным способом для монет США и евро!
Однако, жадный алгоритм иногда может не сработать для внесения изменений.Предположим, у нас есть деноминации [25,15,1] и мы пытаемся заработать 31 цент.Жадный алгоритм выберет 25,1,1,1,1,1,1 (7 монет), в то время как 31 цент на самом деле можно получить как 15,15,1 (3 монеты).
Что яинтересно, есть ли способ заставить жадный алгоритм выйти из строя для ПОДПИСИ монет евро (список монет евро 1,2,5,10,20,50,100,200), которая включает в себя номинал 1. Хотя я могу сделать алгоритм жадностиотказывать подмножества с другими значениями, я не могу заставить его потерпеть неудачу для подмножества монет евро.
В некоторых ресурсах говорится, что жадный алгоритм не будет работать всякий раз, когда самый высокий элемент плюс самый низкий элемент меньше двух развторой по величине элемент (например, в приведенном выше примере 25 + 1 <15 + 15), но сделать это невозможно с помощью подмножества монет евро. </p>