Сигнал задачи
Когда применять
Локальный выбор можно доказуемо включить в оптимальное решение.
Что держать в голове
- Уметь формулировать жадный выбор и его предпосылки.
- Уметь отличать доказанный выбор монеты от угадывания.
Сложность
- Цена зависит от выбора кандидата; типичная схема с предварительной сортировкой занимает O(n log n) времени.
Границы и ошибки
- Локально привлекательный шаг не достаточен: нужен обменный аргумент или другой инвариант, связывающий его с глобальным оптимумом.