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

Ссылки сюда (14) →

Рассмотрим алгоритм, который для любого набора камней произвольного веса разбивает их на две кучи по принципу «очередной камень кладем туда, где суммарный вес меньше». Докажите, что этот приближенный алгоритм имеет мультипликативную ошибку не превышающую 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.

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

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

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