Жадный алгоритм в задаче о рюкзаке/Задачи/Нижняя оценка точности модифицированного жадного — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(не показано 16 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
Приведите пример данных, на которых модифицированный жадный алгоритм дает (хотя бы в пределе) наихудшую оценку точности.
 
Приведите пример данных, на которых модифицированный жадный алгоритм дает (хотя бы в пределе) наихудшую оценку точности.
  
−
[[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>
+

Версия 15:49, 20 мая 2020

Приведите пример данных, на которых модифицированный жадный алгоритм дает (хотя бы в пределе) наихудшую оценку точности.

Источник — «https://discopal.ispras.ru/index.php?title=Жадный_алгоритм_в_задаче_о_рюкзаке/Задачи/Нижняя_оценка_точности_модифицированного_жадного&oldid=11058»