Оптимальность для подзадач. Говоря иными словами, решаемые с помощью жадных алгоритмов задачи обладают свойством оптимальности для подзадач have optimal substructure оптимальное решение всей задачи содержит в себе оптимальные решения подзадач.
С этим свойством мы уже встречались, говоря о динамическом программировании. Например, при доказательстве теоремы 1 мы видели, что если А оптимальный набор заявок, содержащий заявку номер 1, то А A 1 оптимальный набор заявок для меньшего множества заявок S , состоящего из тех заявок, для которых si f1. 6.