Анисимов/Песочница — различия между версиями
Материал из DISCOPAL
(Новая страница: «Сначала докажем, что построенное таким образом множество вершин является вершинным пок…») |
(Решение ex-bounded-knapsack-is-polynomial) |
||
| Строка 1: | Строка 1: | ||
| − | + | <latex> | |
| + | Полиномиальный алгоритм существует. | ||
| − | + | Применим динамическое программирование. Подзадачей будет являться задача "можем ли мы собрать $B$ используя только первые $k\leq n$ чисел?". | |
| − | + | ||
| − | + | Для ответа на этот вопрос будем последовательно составлять множества $S_k$ возможных сумм $\sum_{i=1}^{k}a_{i}x_{i}$ для всех наборов $(x_1,...,x_k)$ из первых $k$ чисел. | |
| + | |||
| + | Изначально множество \[S_0=\{0\}\] | ||
| + | т.к. ничего не взяв, ноль всё равно получим. Следующие строятся по принципу \[S_{i+1} = S_i \cup \{y:\mathbb{Z}|(y-a_{i+1}) \in S_i\}\] | ||
| + | т.е. либо не брать $a_{i+1}$ и возможные суммы те же, либо взять и добавятся новые варианты. | ||
| + | |||
| + | Ответ на исходную задачу определяется предикатом \[B\in S_n\] | ||
| + | |||
| + | Алгоритм полиномиальный. Слагаемые и их количество ограниченны, следовательно и возможные суммы ограниченны. Для множеств $S_k$ \[\forall k:\{1..n\} \forall z:S_k \bullet -n^2*n \leq z \leq n^2*n\] | ||
| + | Размер множеств определяет число операций на каждом построении. Всего строится $n$ множеств, и итоговая сложность алгоритма $O(n^4)$ | ||
| + | </latex> | ||
Текущая версия на 20:26, 19 декабря 2013