Динамическое программирование для задачи о рюкзаке/Задачи/Худший случай для алгоритма с отбором «легких» решений — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Цыганова Светлана, 974гр.)
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(не показано 10 промежуточных версий этого же участника)
Строка 1: Строка 1:
== Цыганова Светлана, 974гр. ==
 
 
Придумайте входные наборы для этого алгоритма, на которых он будет работать экспоненциальное время.
 
Придумайте входные наборы для этого алгоритма, на которых он будет работать экспоненциальное время.
  
<big>Решение:</big>
 
  
<latex>
+
<!--Вообще-то, решения уже есть-->
Алгоритм с отбором "легких" решений работает аналогично алгоритму с отбором "дорогих" решений, только будет запоминать единственную частичную сумму не с данным весом, а с данной стоимостью, те для каждой возможной стоимости набора будем запоминать наилучшую частичную сумму с наименьшим весом.
+
  
Теперь при каких данных алгоритм будет работать экспоненциальное время: при таких же, как и для алгоритма с отбором "дорогих" решений, только теперь все веса предметов из набора будут равны 1, а стоимость будет геометрической прогрессией с $q = 2$:
+
[[Категория:Решенные задачи]]
Список предметов (над чертой стоимость, под чертой вес, обозначения, как в книге):
+
$\frac{1}{1};\frac{2}{1};\frac{4}{1};\frac{8}{1}...\frac{2^n}{1}$. Объем рюкзака будет $B = n$.
+
 
+
Тогда на каждой итерации у нас будет в 2 раза больше новых частичных сумм, чем на предыдущей:
+
 
+
0) $\frac{0}{0}$
+
 
+
1) $\frac{0}{0}; \frac{1}{1}$
+
 
+
2) $\frac{0}{0}; \frac{1}{1}; \frac{2}{0}; \frac{3}{2}$
+
 
+
3) $\frac{0}{0}; \frac{1}{1}; \frac{2}{0}; \frac{3}{2}; \frac{4}{1}; \frac{5}{2}; \frac{6}{2}; \frac{7}{2}$
+
 
+
...
+
 
+
Таким образом каждый раз число частичных сумм увеличивается вдвое, и в конце их становится $2^n$, следовательно, время работы алгоритма становится экспоненциальным (при рассмотре нового элемента надо перебирать все частичные суммы и из всех сумм одной стоимости оставляем самую легкую - это экспоненциальное время).
+
 
+
</latex>
+
 
+
[[Category:На проверку]]
+

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

Придумайте входные наборы для этого алгоритма, на которых он будет работать экспоненциальное время.