Динамическое программирование для задачи о рюкзаке/Задачи/Худший случай для алгоритма с отбором «дорогих» решений — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
Tsyganova (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| + | == Цыганова Светлана, 974гр. == | ||
Придумайте входные наборы для этого алгоритма, на которых он будет работать экспоненциальное время. | Придумайте входные наборы для этого алгоритма, на которых он будет работать экспоненциальное время. | ||
| − | + | <big>Решение:</big> | |
| − | < | + | |
| + | <latex> | ||
| + | Рассмотрим следующий список предметов (над чертой - стоимость, под чертой - вес предмета, обозначения, как в книге): | ||
| + | |||
| + | $\frac{1}{2^0}; \frac{1}{2^1};\frac{1}{2^2};\frac{1}{2^3};\frac{1}{2^4};...\frac{1}{2^n}$ | ||
| + | |||
| + | И пусть вместимость рюкзака будет равна B = 2n | ||
| + | |||
| + | Легко убедиться, что на каждой итерации алгоритма список частичных сумм будет увеличиваться в 2 раза, следовательно в конце работы алгоритма рассмотренных наборов будет $2^{n+1}$. Из этого следует как минимум экспоненциальное время добавление новой частичной суммы, и экспоненциальное время поиска наиболее дорогой частичной суммы. Пример приведен. | ||
| + | |||
| + | Пример на реальных числах, чтобы показать, как число частичных сумм увеличивается вдвое. Возьмем n = 3. Тогда список: $\frac{1}{1}; \frac{1}{2};\frac{1}{4};\frac{1}{8}$, B = 16 | ||
| + | |||
| + | Поитерационный список частичных сумм: | ||
| + | |||
| + | 0) $\frac{0}{0}$ | ||
| + | |||
| + | 1) $\frac{0}{0}; \frac{1}{1}$ | ||
| + | |||
| + | 2) $\frac{0}{0}; \frac{1}{1}; \frac{1}{2}; \frac{2}{3}$ | ||
| + | |||
| + | 3) $\frac{0}{0}; \frac{1}{1}; \frac{1}{2}; \frac{2}{3}; \frac{1}{4}; \frac{2}{5}; \frac{2}{6}; \frac{3}{7}$ | ||
| + | |||
| + | 4) $\frac{0}{0}; \frac{1}{1}; \frac{1}{2}; \frac{2}{3}; \frac{1}{4}; \frac{2}{5}; \frac{2}{6}; \frac{3}{7}; \frac{1}{8}; \frac{2}{9}; \frac{2}{10}; \frac{3}{11}; \frac{2}{12}; \frac{3}{13}; \frac{3}{14}; \frac{4}{15}$ | ||
| + | |||
| + | Итого наборов $2^4$. | ||
| + | |||
| + | </latex> | ||
| + | [[Category:На проверку]] | ||
Версия 11:00, 9 октября 2014
Цыганова Светлана, 974гр.
Придумайте входные наборы для этого алгоритма, на которых он будет работать экспоненциальное время.
Решение: