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

Материал из DISCOPAL
Перейти к: навигация, поиск
(→‎Цыганова Светлана, 974гр.)
Строка 3: Строка 3:
  
 
<big>Решение:</big>
 
<big>Решение:</big>
 +
 +
<latex>
 
Алгоритм с отбором "легких" решений работает аналогично алгоритму с отбором "дорогих" решений, только будет запоминать единственную частичную сумму не с данным весом, а с данной стоимостью, те для каждой возможной стоимости набора будем запоминать наилучшую частичную сумму с наименьшим весом.
 
Алгоритм с отбором "легких" решений работает аналогично алгоритму с отбором "дорогих" решений, только будет запоминать единственную частичную сумму не с данным весом, а с данной стоимостью, те для каждой возможной стоимости набора будем запоминать наилучшую частичную сумму с наименьшим весом.
  
−
Теперь при каких данных алгоритм будет работать экспоненциальное время: при таких же, как и для алгоритма с отбором "дорогих" решений, только теперь все веса предметов из набора будут равны 1, а стоимость будет геометрической прогрессией с q = 2.
+
Теперь при каких данных алгоритм будет работать экспоненциальное время: при таких же, как и для алгоритма с отбором "дорогих" решений, только теперь все веса предметов из набора будут равны 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:На проверку]]
 
[[Category:На проверку]]

Версия 21:02, 9 октября 2014

Цыганова Светлана, 974гр.

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

Решение:

Источник — «https://discopal.ispras.ru/index.php?title=Динамическое_программирование_для_задачи_о_рюкзаке/Задачи/Худший_случай_для_алгоритма_с_отбором_«легких»_решений&oldid=3154»