Алгоритм Рюкзака

Меню сайта

Статистика
Рейтинг@Mail.ru Яндекс.Метрика

Жадный алгоритм для задачи о рюкзаке

Жадный алгоритм для задачи о рюкзаке состоит в следующем (считаем, что все предметы помещаются в рюкзак):
 - Выбрать максимально дорогой предмет, стоимости Cmax .
 - Упорядочить предметы по «удельной стоимости» (стоимости деленной на вес), и набивать рюкзак наиболее «удельно-дорогими» предметами, пока они влезают.

Пусть стоимость этого решения Cgreedy
В зависимости от того, что больше, Cmax или Cgreedy, выбрать первое или второе решение.
Этот алгоритм имеет сложность O(n log(n)), и гарантирует нахождение решения, не хуже чем в два раза от оптимального.

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

 

Принцип жадного выбора

Говорят, что к оптимизационной задаче применим принцип жадного выбора (greedy choice property), если последовательность локально оптимальных (жадных) выборов дает глобально оптимальное решение. Различие между жадными алгоритмами и динамическим программированием можно пояснить так: на каждом шаге жадный алгоритм берет "самый жирный кусок”, а потом уже пытается сделать наилучший выбор среди оставшихся вариантов, каковы бы они ни были. Алгоритм динамического программирования принимает решение, просчитав заранее последствие всех вариантов.

 

Оптимальность для подзадач

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

И жадные алгоритмы, и динамическое программирование основываются на свойстве оптимальности для подзадач, поэтому может возникнуть желание применить жадный алгоритм вместо динамического, и наоборот. В одном случае это может не дать оптимального решения, во втором может привести к менее эффективному решению.

Примером может служить задача о рюкзаке - она состоит в том, чтобы уложить в рюкзак вещи таким образом, чтобы их суммарный вес не превышал предельного значения W и суммарная стоимость вещей была максимальна. Задача имеет две разновидности – непрерывная задача и дискретная. Например, вещи неделимы (золотой слиток) и делимы (золотой песок).

Пусть имеется n вещей, каждая из которых имеет стоимость vi и вес wi.

Стратегия  жадного  алгоритма  состоит  в  следующем:  рассчитывается  удельная  цена  вещи   ci = vi /wi.

Вещи сортируются в порядке убывания удельной цены. Первой выбирается вещь с максимальной удельной ценой, затем  из оставшегося множества снова выбирается вещь с максимальной ценой и т.д. При этом условием выбора является то, что добавляемая вещь не приводит к превышению предельного веса W.

В случае непрерывной задачи о рюкзаке получается общее оптимальное решение, в случае дискретной – нет.

 

Назад Домой Вперед
 
 
Друзья сайта
  • Группа AR в ВК
  • Группа AR в FB
  • Группа AR в OK
  • Алгебра Логики
  • Альтернатива Групп
  • Портал муз. педагога

  • Фрейм


    Алгоритм Рюкзака © 2024 created AD.