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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 4: Строка 4:
  
  
[[Category:Решенные задачи]]
+
[[Category:Нерешенные задачи]]
 
<!--Вообще-то, решения уже есть-->
 
<!--Вообще-то, решения уже есть-->

Версия 07:49, 24 апреля 2014

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