Просмотр исходного текста страницы Динамическое программирование для задачи о рюкзаке/Задачи/ex-bounded-knapsack-is-polynomial

<latex>
\small
Рассмотрим некоторую модификацию задачи «Рюкзак-выполнимость», разрешим даже отрицательные размеры.
Формально:
\begin{itemize}
    \item Даны целые числа $a_i, \ \ \forall i \in [1 \ldots n] \ -n^2 \leq a_i \leq n^2 $ и~число~$B$.
    \item Найти ответ на <<Существует ли решение в~0--1 переменных $(x_1, \ldots, x_n)$ уравнения $\sum_{i=1}^n a_i x_i=B$?>>.
\end{itemize}
Существует ли полиномиальный алгоритм для этой задачи?
</latex>


<!--Вообще-то, решения уже есть-->

[[Категория:Задачи]]