Жадные алгоритмы: как работают и когда дают неверный ответ

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

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

Оптимальный ответ получается, только если выполнены два условия:

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

Если оба условия есть, жадный алгоритм прост и быстр — обычно всё упирается в сортировку, O(n log n). Если нет — алгоритм всё равно вернёт какой-то ответ, просто не лучший, и ничто об этом не предупредит.

Сдача монетами: работает не для любого набора

Задача: набрать сумму минимальным числом монет. Жадное правило: всегда брать самую крупную монету, которая помещается.

def greedy_coins(amount, coins):
    result = []
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c
            result.append(c)
    return result

С монетами 1, 5, 10, 25 и суммой 30 получаем 25 + 5 — оптимально. Наборы, где жадный алгоритм всегда даёт оптимум, называют каноническими, и многие реальные валюты устроены именно так.

Теперь монеты 1, 3, 4 и сумма 6:

• Жадно: 4 + 1 + 1 — три монеты.
• Оптимально: 3 + 3 — две монеты.

Первый «лучший» выбор (4) испортил всё остальное. Для произвольного набора монет нужно динамическое программирование: посчитать минимальное число монет для каждой суммы от 0 до целевой.

def min_coins(amount, coins):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else -1

Расписание встреч: сортировка по времени окончания

Задача: выбрать максимальное число непересекающихся встреч для одной переговорной.

Правильное жадное правило — брать встречу, которая заканчивается раньше всех, затем повторять для встреч, начинающихся после её окончания.

def max_meetings(intervals):
    count, last_end = 0, float("-inf")
    for start, end in sorted(intervals, key=lambda x: x[1]):
        if start >= last_end:
            count += 1
            last_end = end
    return count

Почему работает: раннее окончание оставляет больше всего места для остальных. Важно именно правило — «сначала самые короткие» или «сначала самые ранние по началу» выглядят разумно, но ломаются на простых примерах. Если у встреч есть веса (одни ценнее других), жадность уже не работает, нужна DP по отсортированным интервалам.

Кодирование Хаффмана: объединяем два самых редких

Код Хаффмана строит оптимальный префиксный код для сжатия: частые символы получают короткие коды, редкие — длинные.

1. Положите каждый символ с его частотой в очередь с приоритетом.
2. Достаньте два самых редких узла и объедините в новый узел с суммарной частотой.
3. Верните его в очередь и повторяйте, пока не останется одно дерево.
4. Прочитайте коды от корня: левое ребро — 0, правое — 1.

Жадный выбор — объединять два самых редких символа — доказуемо безопасен: в некотором оптимальном дереве они являются соседями на самом глубоком уровне. Код Хаффмана входит в формат DEFLATE, который используется в ZIP и PNG.

Когда жадность ошибается и нужна DP

Рюкзак 0/1 — классическая ловушка. Вместимость 50, предметы (вес, ценность): (10, 60), (20, 100), (30, 120). Жадный выбор по ценности на килограмм берёт первые два и получает 160. Лучший ответ — второй и третий, 220. В дробном рюкзаке, где можно взять часть предмета, то же жадное правило оптимально.

Как проверить жадную идею

• Ищите маленький контрпример. Переберите крошечные входы вручную или сравните с полным перебором в быстром тесте.
• Попробуйте аргумент обмена. Возьмите любое оптимальное решение и покажите, что его первый шаг можно заменить жадным без ухудшения.
• Настораживайтесь при весах и предметах «всё или ничего». Они чаще всего ломают жадные правила.
• Если сомневаетесь, сначала напишите DP, а потом посмотрите, не упрощается ли она до жадного правила.