Когда жадный алгоритм даёт оптимальное решение?

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

Когда жадность корректна

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

Классика: выбор заявок по времени окончания, коды Хаффмана, минимальное остовное дерево (Краскал, Прим), Дейкстра при неотрицательных весах.

Где жадность ломается

• Рюкзак с неделимыми предметами: максимум цены за килограмм не даёт оптимума — нужна ДП.
• Размен монет жадно работает не для произвольной системы номиналов.

Как доказывать корректность

• Exchange argument: показать, что любой оптимум превращается в жадный без ухудшения.
• Индукция по шагам выбора.

Коротко для собеседования

Жадный алгоритм фиксирует локально лучший выбор и не пересматривает его, поэтому он быстр, но корректен лишь при свойстве жадного выбора. Прежде чем применять, докажите это обменным аргументом или найдите контрпример — как в рюкзаке 0/1, где нужна ДП.