Жадные алгоритмы

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

Задача "Размен монет"

Монетная система некоторого государства состоит из монет достоинством $a_1 = 1 < a_2 < \ldots < a_n$. Требуется выдать сумму $S$ наименьшим возможным количеством монет.

Жадный алгоритм решения этой задачи таков. Берётся наибольшее возможное количество монет достоинства $a_n : x_n = \lfloor \frac{S}{a_n} \rfloor$. Таким же образом получаем, сколько нужно монет меньшего номинала, и т. д.

Для данной задачи жадный алгоритм не всегда даёт оптимальное решение, а только для некоторых, называемых каноническими, монетных систем, вроде используемых в США ($1$, $5$, $10$, $25$ центов). Неканонические системы таким свойством не обладают. Так, например, сумму в $24$ копейки монетами в $1$, $5$ и $7$ коп. жадный алгоритм разменивает так: $7$ коп. — $3$ шт., $1$ коп. — $3$ шт., в то время как правильное решение — $7$ коп. — $2$ шт., $5$ коп. — $2$ шт.

Пример

У кассира есть бесконечное количество монет номиналами $1$, $5$, $10$. Выведите минимальное количество монет, чтобы выдать сдачу $money$.

Решение:

Рассмотрим основную идею решения. Пока сдача положительна $money > 0$, мы выбираем монету с самым большим номиналом, не превышающем $money$, отнимаем значение номинала выбранной монеты от $money$ и увеличиваем количество монет:

money = int(input())

cnt = 0
while money > 0:
  if money >= 10:
    money -= 10
  elif money >= 5:
    money -= 5
  else:
    money -= 1
  cnt += 1

print(f"{cnt}")

26
4

Также эту задачу можно решить в одну строку:

cnt = money // 10 + money % 10 // 5 + money % 5

Проектировать жадные алгоритмы просто, но вот доказывать их правильность — нередко сложная задача.

Задача "Специи"

Вор пробрался в лавку специй и нашёл там четыре фунта шафрана, три фунта ванили и пять фунтов корицы. В его рюкзак можно сложить до девяти фунтов, поэтому забрать всё он не сможет. Предположим, что цены на шафран, ваниль и корицу $$5000$, $$200$ и $$10$ соответственно. Как унести максимально дорогую добычу? Если вор заберёт $u_1$ фунтов шафрана, $u_2$фунтов ванили и $u_3$ фунтов корицы, общая ценность украденного составит $5000 \cdot \frac{u_1}{4} + 200 \cdot \frac{u_2}{3} + 10 \cdot \frac{u_3}{5}.$ Вор хотел бы найти максимальное значение этого выражения при следующих ограничениях: $u_1 \leq 4, u_2 \leq 3, u_3 \leq 5, u_1 + u_2 + u_3 \leq 9.$

Решение:

Определим цену специи $i$ как $\frac{c_i}{w_i}$. Естественной стратегией для вора было бы брать как можно больше самой дорогой специи.

Чтобы доказать, что эта стратегия приводит к оптимальному решению, рассмотрим самую дорогую специю $m$. Каков максимальный объём $a$ $m$-й специи, который вор может положить в рюкзак?

Во-первых, она должна уместиться в рюкзак: $a \leq W.$

Во-вторых, она не должна превышать доступный объём $m$-й специи: $a \leq w_m.$

Следовательно, $a = min(w_m, W)$ Мы утверждаем, что существует оптимальное решение, включающее в себя $a$ фунтов $m$-й специи.

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

Задача "Рекламная кампания"

Представим, что вы владелец популярной страницы в интернете, на которой есть $n = 3$ рекламных мест. Вы хотите продать их рекламодателям, которые рассчитывают на $clikcs_1 = 10, clikcs_2 = 20, clikcs_3 = 30$ кликов в день и при этом готовы платить $price_1 = 2, price_2 = 3, price_3 = 5$ за клик. Как подобрать пары рекламных мест и рекламодателей так, чтобы получить максимальную прибыль?

Например, доход от отмеченных голубым цветом пар, приведённых выше, составит $10 \cdot 5 + 20\cdot 2 + 30\cdot 3 = 180$ долларов; от отмеченных чёрным — $10 \cdot 3 + 20\cdot 5 + 30\cdot 2 = 190.$

Решение:

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

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

Задача "Составление расписания"

Допустим, имеется учебный класс, в котором нужно провести как можно больше уроков. Вы получаете список уроков:

Провести в классе все уроки не получится, потому что некоторые из них перекрываются по времени.

Требуется провести в классе как можно больше уроков. Как отобрать уроки, чтобы полученный набор оказался самым большим из возможных?

Вроде бы сложная задача, верно? На самом деле алгоритм оказывается на удивление простым. Вот как он работает:

1. Выбрать урок, завершающийся раньше всех. Это первый урок, который будет проведен в классе.

2. Затем выбирается урок, начинающийся после завершения первого урока. И снова следует выбрать урок, который завершается раньше всех остальных. Он становится вторым уроком в расписании.

Продолжайте действовать по тому же принципу - и вы получите ответ! Давайте попробуем. Рисование заканчивается раньше всех уроков (в 10:00), поэтому мы выбираем именно его. Теперь нужно найти следующий урок, который начинается после 10:00 и завершается раньше остальных. Английский язык отпадает - он перекрывается с рисованием, но математика подходит. Наконец, информатика перекрывается с математикой, но музыка подходит.

Итак, эти три урока должны проводиться в классе.

Может показаться, что алгоритм слишком очевиден, а значит, должен быть неправильным. Но в этом и заключается красота жадных алгоритмов: они просты! Жадный алгоритм прост: на каждом шаге он выбирает оптимальный вариант. В нашем примере при выборе урока выбирается тот урок, который завершается раньше других. В технической терминологии: на каждом шаге выбирается локально-оптимальное решение, а в итоге вы получаете глобально-оптимальное решение. Хотите верьте, хотите нет, но этот простои алгоритм успешно находит оптимальное решение задачи составления расписания!

Практические задания

Авторизация