Жадный алгоритм в задаче о рюкзаке/Задачи/Нижняя оценка точности модифицированного жадного — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
Строка 1: | Строка 1: | ||
Приведите пример данных, на которых модифицированный жадный алгоритм дает (хотя бы в пределе) наихудшую оценку точности. | Приведите пример данных, на которых модифицированный жадный алгоритм дает (хотя бы в пределе) наихудшую оценку точности. | ||
− | [[Category: | + | [[Category:На проверку]] |
− | < | + | |
+ | <m> | ||
+ | |||
+ | Рассмотрим последовательность объектов со стоимостями $c_i = 2^i$, и объемами $v_i = 3^i$ соответственно. | ||
+ | Пусть $i = 0,\dots, m+1$ и объем рюкзака равен $V = \sum_{i = 1}^{m+1}3^i$. Тогда оптимальный алгоритм должен положить | ||
+ | в рюкзак объекты с индексами $t = 1,\dots,m+1$. Суммарная стоимость такого рюкзака равна $S_{opt} = 2^{m+2} - 2$. | ||
+ | Жадный алгоритм выберет объекты с индексами $i = 0,\dots, m$, так как дальше отсортированные по убыванию относительной | ||
+ | цены объекты перестанут влазить в рюкзак. Стоимость такого рюкзака равна $S_g = 2^{m+1}-1$. Модифицированный жадный алгоритм будет | ||
+ | отвечать $S_g^* = max(2^{m+1}, S_g) = max(2^{m+1}, 2^{m+1}-1) = 2^{m+1}$. | ||
+ | Отсюда получается, что | ||
+ | $$ | ||
+ | \frac{S_{opt}}{S_g^*} = \frac{2^{m+2} - 2}{2^{m+1}} = 2 - 2^{-m}\to 2 | ||
+ | $$ | ||
+ | |||
+ | |||
+ | </m> |
Версия 14:11, 26 октября 2014
Приведите пример данных, на которых модифицированный жадный алгоритм дает (хотя бы в пределе) наихудшую оценку точности.