Жадный алгоритм (Greedy Algorithms) - на каждом шагу делает локально оптимальный выбор в расчете на то,
что итоговое решение также будет оптимальным.
Это не всегда оправдано, но для многих задач жадные алгоритмы действительно дают оптимум.
Временная сложность данного алгоритма — O(N).
Задача о рюкзаке(Нужно унести набор товаров максимальной стоимости, которые только влезут в рюкзак):
1)Выбрать максимально дорогой предмет из еще не затронутых.
2) Если он помещается в рюкзак, положить его туда, если нет — пропускаем.
3)Все предметы перебрали? Если нет — возвращаемся к 1 пункту, если да — бежим из магазина, так как наша цель тут выполнена.