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

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

Версия 15:49, 20 мая 2020

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