Жадность и почему ей нельзя верить

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

В этом вся сила и вся беда. Сила — в том, что такой алгоритм короткий и быстрый. Беда — в том, что «выгодно сейчас» и «выгодно в итоге» совпадают далеко не всегда, а на маленьких примерах разница не видна.

Пример, где жадность работает

Монеты номиналом 1, 5, 10 и 25. Набрать сумму $x$ наименьшим числом монет.

Жадный ход: берём как можно больше самых крупных, потом следующих по величине, и так далее.

int coins = 0;
for (int value : {25, 10, 5, 1}) { coins += x / value; x %= value; }

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

Пример, где та же жадность неверна

Замените номиналы на 1, 3 и 4, а сумму возьмите 6.

Жадность берёт четвёрку, потом две единицы — три монеты. Правильный ответ — две тройки, то есть две монеты.

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

Почему это не ловится примерами

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

Отсюда правило: жадное решение без доказательства или без стресс-теста считается непроверенным, даже если оно прошло примеры и кажется очевидным.

Две вещи, которые стоит уметь

Про жадность полезно уметь две противоположные вещи.

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

Ломать. То есть за минуту находить контрпример или убеждаться, что его нет. Это, пожалуй, полезнее: жадная идея приходит в голову сама, и главный вопрос не «как доказать», а «а не вранья ли это».

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

Как распознать задачу на жадность

Приметы нечёткие, но есть:

• ответ строится по шагам, и на каждом шаге видно, что выгодно;
• есть естественный порядок, в котором объекты хочется рассмотреть — по времени, по весу, по отношению;
• задача формулируется как «максимум чего-то» или «минимум чего-то» при ограничениях, но динамика по состояниям выглядит слишком тяжёлой.

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