Прочитайте описание принципа жадного выбора и расставьте этапы доказательства оптимальности в правильном порядке.

К оптимизационной задаче применим принцип жадного выбора, если последовательность локально оптимальных выборов даёт глобально оптимальное решение.

В типичном случае доказательство оптимальности следует такой схеме:

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