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

Что такое жадный алгоритм?

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

Всё проще понять на примере

Представьте, что вы и ваш друг — члены клуба любителей кино. На одном из собраний друг предлагает вам пари: кто из вас посмотрит больше фильмов за определённый период времени. Вы согласились на дружеский спор и обозначили следующие условия: за 120 часов необходимо просмотреть максимальное количество фильмов, всего для просмотра выбрано 10 кинокартин. У каждого фильма есть своя продолжительность (в часах), опишем этот пункт в виде массива [100, 5, 1, 98, 15, 43, 7, 77, 41, 56] (каждый элемент массива обозначает время просмотра фильма). Так как это выдуманная ситуация, то вы и ваш друг в течение следующих 120 часов могут только смотреть представленные фильмы.

Наша задача — посмотреть максимальное количество фильмов за фиксированное время, чтобы выполнить это, вы в первую очередь сортируете продолжительность фильмов по возрастанию. Далее начинаете смотреть фильмы по уже отсортированному списку от наименьшего к максимальному, пока время спора не истечет. По такой тактике вы успеете просмотреть фильмы следующей продолжительностью [1, 5, 7, 15, 41, 43]

Ваш выдуманный друг не придерживался тактики и просто смотрел фильмы в случайном порядке [1, 77, 41]

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

Рассмотрим более практический пример с написанием кода

Решим задачу с платформы LeetCode.

Условие: вы продаете лимонад, стакан которого стоит 5 условных единиц. Покупатели расплачиваются за лимонад монетами номиналом 5, 10, 20 у.е. Наша задача - понять, сможем ли мы дать сдачу всем покупателям, если это потребуется, при условии, что изначально у нас ни одной монеты. 

Примеры:

Входные данные: [5, 5, 5, 10, 20]
Выходные данные: True

Входные данные: [5, 5, 10, 10, 20]
Выходные данные: False

Решение с использованием жадного подхода (функция lemonadeChange):

def lemonadeChange(bills):
    """
    :type bills: List[int]
    :rtype: bool
    """
    count5, count10 = 0, 0
    for b in bills:
        if b == 5:
            count5 += 1
        elif b == 10:
            if count5 == 0:
                return False
            count5 -= 1
            count10 += 1
        else:
            if count10 > 0 and count5 > 0:
                count10 -= 1
                count5 -= 1
            elif count5 >= 3:
                count5 -= 3
            else:
                return False
    return True

Идея решения заключается в том, чтобы на каждом шаге «погашать» сдачу монетой с максимальным возможным номиналом. Например, наш баланс [5, 5, 10], следующая монета, которой расплатились, равна 20. Тогда изначально оптимальным способом будет взять одну монету номиналом 10 у.е., далее монету с номиналом 5 у.е.

Почему не стоит изначально платить монетами с номиналом 5? 

Ответ на данный вопрос можно найти, разобрав следующий пример. Представим, что баланс состоит из следующих монет: [5, 5, 5, 10]. Приходит покупатель и расплачивается монетой 20 у.е. Попробуем вернуть сдачу преимущественно пятаками. Мы отдаем три монеты номиналом 5 у.е., соответственно наш баланс выглядит следующим образом: [10, 20]. Если следующий покупатель расплатится монетой больше, чем 5, то отдать сдачу не получится.

Вывод: слепое следование локально оптимальному выбору не гарантирует нахождение верного глобального решения. Применение жадного алгоритма требует от себя доказательства корректности.

Почему стоит использовать жадный алгоритм? 

Первое - это, конечно, простота и понятность. Часто жадные алгоритмы имеют несложную реализацию и основываются на интуиции. Также алгоритм часто эффективен при сложности в O(n) или O(n logn) (в случае сортировки) и выполняется за один проход по циклу.

Для жадного алгоритма важно следующее:

1. сделать локально-оптимальный выбор с целью получить итоговый ответ

2. не возвращаться к пересмотру ранее принятых решений

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