Жадный алгоритм в задаче о рюкзаке/Задачи/Greedy-Subset-Sum — различия между версиями
StasFomin (обсуждение | вклад) |
|||
| Строка 1: | Строка 1: | ||
| − | Рассмотрим алгоритм, который для любого набора камней произвольного веса разбивает их на две кучи | + | Рассмотрим алгоритм, который для любого набора камней произвольного веса разбивает их на две кучи по принципу «очередной камень кладем туда, где суммарный вес меньше». Докажите, что этот приближенный алгоритм имеет мультипликативную ошибку не превышающую 2 (целевая функция — минимизировать вес всех камней в максимальной куче). |
| − | по принципу «очередной камень кладем туда, где суммарный вес меньше». | + | |
| − | Докажите, что этот приближенный алгоритм имеет мультипликативную ошибку не превышающую 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. | ||
Версия 12:34, 26 сентября 2014
Рассмотрим алгоритм, который для любого набора камней произвольного веса разбивает их на две кучи по принципу «очередной камень кладем туда, где суммарный вес меньше». Докажите, что этот приближенный алгоритм имеет мультипликативную ошибку не превышающую 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.