Участник:Jzargo/Greedy-Subset-Sum

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

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

Из условия задачи подразумевается, что мы можем сортировать камушки, иначе оценка ниже просто не работает.

StasFomin 16:51, 15 мая 2019 (MSK): В условии мы не сортируем камни. Если вы можете обосновать, что этот алгоритм не достигает точности 2 (что требовалось в задаче) — приведите пример.


Сам алгоритм прост: 1. берём камушки из отсортированного списка и закидываем в кучу, вес которой меньше. Конец.

Итоговая аппроксимация это 7/6 <2. (да и 2 это совсем грубая ошибка, хоть на рандом раскидывать камни).

Доказательство лучше господина Рона Гракхама (https://pdfs.semanticscholar.org/c037/edd22215b89c8d2924d4e3c81eb84fdadec7.pdf) я не придумаю, тем более оно обобщает эту задачу (и на него даже википедия ссылается) https://ru.wikipedia.org/wiki/Задача_разбиения_множества_чисел