Жадный алгоритм в задаче о рюкзаке/Задачи/Greedy-Subset-Sum — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена :Решенные задачи]] на :Нерешенные задачи]]) |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
Рассмотрим алгоритм, который для любого набора камней произвольного веса разбивает их на две кучи | Рассмотрим алгоритм, который для любого набора камней произвольного веса разбивает их на две кучи | ||
по принципу «очередной камень кладем туда, где суммарный вес меньше». | по принципу «очередной камень кладем туда, где суммарный вес меньше». | ||
| − | Докажите, что этот приближенный алгоритм имеет мультипликативную ошибку не превышающую 2 (целевая функция — минимизировать вес всех камней в | + | Докажите, что этот приближенный алгоритм имеет мультипликативную ошибку не превышающую 2 (целевая функция — минимизировать максимальный вес всех камней в обоих кучах). |
| + | |||
| − | |||
<!--Вообще-то, решения уже есть--> | <!--Вообще-то, решения уже есть--> | ||
| + | |||
| + | [[Категория:Нерешенные задачи]] | ||
Версия 13:27, 8 декабря 2016
Рассмотрим алгоритм, который для любого набора камней произвольного веса разбивает их на две кучи по принципу «очередной камень кладем туда, где суммарный вес меньше». Докажите, что этот приближенный алгоритм имеет мультипликативную ошибку не превышающую 2 (целевая функция — минимизировать максимальный вес всех камней в обоих кучах).