Жадный алгоритм в задаче о рюкзаке/Задачи/Нижняя оценка точности модифицированного жадного — различия между версиями
Материал из 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
Приведите пример данных, на которых модифицированный жадный алгоритм дает (хотя бы в пределе) наихудшую оценку точности.