|
|
| Строка 1: |
Строка 1: |
| − | == Цыганова Светлана, 974гр. ==
| |
| | Придумайте входные наборы для этого алгоритма, на которых он будет работать экспоненциальное время. | | Придумайте входные наборы для этого алгоритма, на которых он будет работать экспоненциальное время. |
| | | | |
| − | <big>Решение:</big>
| + | [[Category:Решенные задачи]] |
| − | | + | <!--Вообще-то, решения уже есть--> |
| − | <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:На проверку]]
| + | |
Придумайте входные наборы для этого алгоритма, на которых он будет работать экспоненциальное время.