Как ломать жадность

Жадная идея приходит в голову сама, и главный вопрос не «как её доказать», а «не вранья ли это». Быстрее всего отвечает на него не размышление, а запуск.

Схема стресс-теста

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

import random

for attempt in range(10000):
    n = random.randint(1, 8)                     # маленькие входы!
    a = [random.randint(1, 10) for _ in range(n)]
    fast = greedy(a)
    slow = brute_force(a)
    if fast != slow:
        print("контрпример:", a, "жадность:", fast, "перебор:", slow)
        break

Три условия, без которых это не работает:

Входы должны быть маленькими. На $n = 8$ перебор мгновенен, а контрпример — если он есть — почти наверняка найдётся среди коротких. Большие входы только замедлят поиск и дадут контрпример, в котором ничего не разберёшь.

Значения должны быть маленькими. Числа от 1 до 10 дают повторы, нули, равенства — ровно те случаи, на которых жадность обычно и ломается. С числами до миллиарда все элементы различны, и половина крайних случаев не встретится никогда.

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

Чего стресс-тест не заменяет

Есть распространённая ошибка: сравнить две свои реализации одной идеи и счесть совпадение проверкой.

Так не выйдет. Если идея неверна, обе реализации будут неверны одинаково, и сверка покажет полное согласие. Она поймает опечатку, но не поймает то, ради чего затевалась.

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

Как писать перебор

Для задачи о расписании — все подмножества заявок, проверить совместимость, взять наибольшее по размеру:

def brute_force(segments):
    n = len(segments)
    best = 0
    for mask in range(1 << n):
        chosen = [segments[i] for i in range(n) if mask >> i & 1]
        chosen.sort()
        ok = all(chosen[i][1] < chosen[i + 1][0] for i in range(len(chosen) - 1))
        if ok:
            best = max(best, len(chosen))
    return best

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

Что делать с контрпримером

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

Дальше два пути. Либо понять, чего не хватает жадности, и поправить порядок сортировки — тогда стресс запускается снова. Либо признать, что жадность здесь не работает, и переходить к динамике.

Классические поломки

Идеи, которые выглядят правдоподобно и неверны:

Задача	Соблазнительная жадность	Что не так
Монеты произвольных номиналов	брать самые крупные	1, 3, 4 и сумма 6
Рюкзак с весами и ценностями	брать по убыванию отношения	предмет с лучшим отношением может не влезть выгодно
Непересекающиеся отрезки	брать самые короткие	короткий на стыке выбивает два длинных
Разбиение на пары	брать первого подходящего	заберёт того, кто был нужен другому
Раскраска	брать первый свободный цвет	зависит от порядка обхода

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