Жадный алгоритм для задачи о рюкзаке состоит в следующем (считаем, что все предметы помещаются в рюкзак): - Выбрать максимально дорогой предмет, стоимости Cmax . - Упорядочить предметы по «удельной стоимости» (стоимости деленной на вес), и набивать рюкзак наиболее «удельно-дорогими» предметами, пока они влезают.
Пусть стоимость этого решения Cgreedy В зависимости от того, что больше, Cmax или Cgreedy, выбрать первое или второе решение. Этот алгоритм имеет сложность O(n log(n)), и гарантирует нахождение решения, не хуже чем в два раза от оптимального.
Для многих оптимизационных задач есть более простые и быстрые алгоритмы, чем динамическое программирование. К таким алгоритмам относятся жадные алгоритмы. Жадный алгоритм на каждом шаге делает локально оптимальный выбор в расчете на то, что итоговое решение также будет оптимальным. Это не всегда оправдано, но для многих задач жадные алгоритмы действительно дают оптимум.
Принцип жадного выбора
Говорят, что к оптимизационной задаче применим принцип жадного выбора(greedy choice property), если последовательность локально оптимальных (жадных) выборов дает глобально оптимальное решение. Различие между жадными алгоритмами и динамическим программированием можно пояснить так: на каждом шаге жадный алгоритм берет "самый жирный кусок”, а потом уже пытается сделать наилучший выбор среди оставшихся вариантов, каковы бы они ни были. Алгоритм динамического программирования принимает решение, просчитав заранее последствие всех вариантов.
Оптимальность для подзадач
Решаемые с помощью жадных алгоритмов задачи обладают свойством оптимальности для подзадач: оптимальное решение всей задачи содержит оптимальное решение подзадач.
И жадные алгоритмы, и динамическое программирование основываются на свойстве оптимальности для подзадач, поэтому может возникнуть желание применить жадный алгоритм вместо динамического, и наоборот. В одном случае это может не дать оптимального решения, во втором может привести к менее эффективному решению.
Примером может служить задача о рюкзаке - она состоит в том, чтобы уложить в рюкзак вещи таким образом, чтобы их суммарный вес не превышал предельного значения W и суммарная стоимость вещей была максимальна. Задача имеет две разновидности – непрерывная задача и дискретная. Например, вещи неделимы (золотой слиток) и делимы (золотой песок).
Пусть имеется n вещей, каждая из которых имеет стоимость vi и вес wi.
Стратегия жадного алгоритма состоит в следующем: рассчитывается удельная цена вещи ci = vi /wi.
Вещи сортируются в порядке убывания удельной цены. Первой выбирается вещь с максимальной удельной ценой, затем из оставшегося множества снова выбирается вещь с максимальной ценой и т.д. При этом условием выбора является то, что добавляемая вещь не приводит к превышению предельного веса W.
В случае непрерывной задачи о рюкзаке получается общее оптимальное решение, в случае дискретной – нет.