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