Жадный метод

Рассмотрим задачу о размене. В США используются монеты достоинством 25, 10, 5 и 1 цент. Как дать такими монетами сдачу, например, в 48 центов? На первом шаге вы можете выбрать монету любого номинала из четырех приведенных. "Жадное" мышление приводит вас к мысли, что это должна быть монета в 25 центов, что максимально снизит остающуюся к выдаче сумму — а именно до 23 центов. На втором шаге наилучшим выбором оказывается выбор монеты в 10 центов, что снижает сумму до 13 центов. Еще один выбор монеты в 10 центов приводит нас к остатку в 3 цента, которые можно дать только тремя монетами по 1 центу.

Является ли это решение экземпляра задачи о размене оптимальным? Да. Можно доказать, что жадный алгоритм для данных номиналов монет дает оптимальное решение для любой суммы, выражающейся натуральным числом.

Но можно привести пример необычных номиналов монет (например, 7,5,1), которые для определенных сумм могут дать неоптимальные решения.

Рассмотренный подход к решению задачи о размене называется жадным. Жадный подход предполагает построение решения посредством выбора последовательности шагов, на каждом из которых получается частичное решение поставленной задачи, пока не будет получено полное решение. При этом на каждом шаге выбор должен быть

• допустимым, т.е. удовлетворять ограничениям задачи;
• локально оптимальным, т.е. наилучшим локальным выбором среди всех допустимых вариантов, доступных на каждом шаге;
• окончательным, т.е. будучи сделан, он не может быть изменен последующими шагами алгоритма.

Эти требования поясняют название метода: на каждом шаге он предполагает "жадный" выбор наилучшей доступной альтернативы в надежде, что последовательность локально оптимальных выборов приведет к (глобально) оптимальному решению всей задачи.

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

Задания для практики

1. Напишите псевдокод жадного алгоритма для задачи о размене для суммы `S` и монет с номиналами `d_1 > d_2 > ...> d_m` в качестве входных данных. Чему равна временная эффективность вашего алгоритма как функция от `S`?
2. Приведите пример экземпляра задачи о размене, для которой жадный алгоритм не дает оптимального решения.