Просмотр исходного текста страницы Анисимов/Песочница

<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>