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

Материал из DISCOPAL
< Жадный алгоритм в задаче о рюкзаке‎ | Задачи
Версия от 09:58, 25 февраля 2016; StasFomin (обсуждение | вклад) (Массовая правка: замена :Решенные задачи]] на :Нерешенные задачи]])

Перейти к: навигация, поиск

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

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.