Жадный алгоритм в задаче о рюкзаке/Задачи/Greedy-Subset-Sum — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 1: Строка 1:
Рассмотрим алгоритм, который для любого набора камней произвольного веса разбивает их на две кучи
+
Рассмотрим алгоритм, который для любого набора камней произвольного веса разбивает их на две кучи по принципу «очередной камень кладем туда, где суммарный вес меньше». Докажите, что этот приближенный алгоритм имеет мультипликативную ошибку не превышающую 2 (целевая функция — минимизировать вес всех камней в максимальной куче).
по принципу «очередной камень кладем туда, где суммарный вес меньше».
+
Докажите, что этот приближенный алгоритм имеет мультипликативную ошибку не превышающую 2 (целевая функция — минимизировать вес всех камней в максимальной куче).
+
  
 +
== Стенина Мария, группа 974 ==
  
[[Category:Нерешенные задачи]]
+
[[Категория:На проверку]]
<!--Вообще-то, решения уже есть-->
+
 
 +
Заметим, что в любой момент работы алгоритма разница весов более и менее тяжелых куч не превосходит веса самого тяжелого камня.
 +
 
 +
MaxA = max A_i.
 +
 
 +
Пусть M* — минимально возможный вес более тяжелой кучи. И M — вес более тяжелой кучи, получившейся у жадного алгоритма, а m — вес более легкой кучи у жадного алгоритма.
 +
 
 +
Имеют место неравенства
 +
 
 +
M* >= m
 +
 
 +
M* >= MaxA
 +
 
 +
Оцениваем отношение веса тяжелой кучи жадного алгоритма и оптимального веса
 +
 
 +
M / M* <= (m + MaxA) / M* <= (M* + MaxA) / M* = 1 + MaxA / M* <= 2.

Версия 12:34, 26 сентября 2014

Рассмотрим алгоритм, который для любого набора камней произвольного веса разбивает их на две кучи по принципу «очередной камень кладем туда, где суммарный вес меньше». Докажите, что этот приближенный алгоритм имеет мультипликативную ошибку не превышающую 2 (целевая функция — минимизировать вес всех камней в максимальной куче).

Стенина Мария, группа 974

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

MaxA = max A_i.

Пусть M* — минимально возможный вес более тяжелой кучи. И M — вес более тяжелой кучи, получившейся у жадного алгоритма, а m — вес более легкой кучи у жадного алгоритма.

Имеют место неравенства

M* >= m

M* >= MaxA

Оцениваем отношение веса тяжелой кучи жадного алгоритма и оптимального веса

M / M* <= (m + MaxA) / M* <= (M* + MaxA) / M* = 1 + MaxA / M* <= 2.