Методика «жадные алгоритмы» (Определение. Алгоритмы и задачи : задача о размене денег)

Жадный алгоритм (англ. Greedy algorithm) — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным.

Задача о размене денег

Эта задача постоянно встает перед миллионами кассиров во всем мире: как выплатить сумму N при помощи наименьшего количества монет номиналом использующимся в той или иной стране.  Например, в США широко распространены монеты достоинством d1=25 центов, d2=10 центов, d3=5 центов и d4=1 цент. Как сдать такими сдачу, например, в 48 центов? Если вы ответите, что это одна монета в 25 центов, две - по 10 центов и три – по 1 центу, то, сознательно или нет, вы следуете стратегии, которая позволяет сделать оптимальный выбор среди возможных альтернатив. На первом шаге вы можете выбрать монету любого номинала из 4 приведенных. «Жадное» мышление приводит вас к мысли, что это должна быть монета в 25 центов, что максимально снизит остающуюся к выдаче сумму – а именно до 23 центов. На втором шаге вы уже не можете выбрать монету в 25 центов, поскольку это нарушило бы ограничения, поставленные в условии задачи. Поэтому наилучшим выбором в данной ситуации оказывается выбор монеты в 10 центов, что снижает сумму до 13 центов. Еще один выбор монеты в 10 центов приводит к остатку в 3 цента, которые можно дать только тремя монетами по 1 центу.

Главные условия:

Выбор должен быть

·         Допустимым, т.е. удовлетворять ограничениям задачи;

·         Локально оптимальным, т.е. наилучшим локальным выбором среди всех допустимых вариантов, доступных на каждом шаге;

·         Окончательным, т.е. будучи сделан, он не может быть изменен последующими шагами алгоритма.

Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.