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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: добавление Категория:Теоретические задачи)
 
(не показано 18 промежуточных версий этого же участника)
Строка 1: Строка 1:
Рассмотрим алгоритм, который для любого набора камней произвольного веса разбивает их на две кучи по принципу «очередной камень кладем туда, где суммарный вес меньше». Докажите, что этот приближенный алгоритм имеет мультипликативную ошибку не превышающую 2 (целевая функция — минимизировать вес всех камней в максимальной куче).
+
Рассмотрим алгоритм, который для любого набора камней произвольного веса разбивает их на две кучи
 +
по принципу «очередной камень кладем туда, где суммарный вес меньше».
 +
Докажите, что этот приближенный алгоритм имеет мультипликативную ошибку не превышающую 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.
+

Текущая версия на 06:50, 4 мая 2023

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