Задача о рюкзаке NP-трудна

[max(Im)]

Задача о рюкзаке рассматривается в такой формулировке: максимизировать $\sum c_j x_j$ по целым $x_j$ при условии $\sum w_jx_j \leqslant K$ (суммы от 1 до $n$).

Задача является NP-трудной, ну то есть если бы для нее существовал полиномиальный алгоритм, то существовал бы для любой задачи из NP.

Обычно NP-трудность некоторой задачи $A$ доказывают построением полиномиального алгоритма для какой-нибудь NP-полной задачи в предположении существования полиномиального алгоритма для $A.$ Как быть с задаче о рюкзаке в этом случае?

Обычно рассматривается целочисленный рюкзак (существуют ли целые $x_j$, такие что $\sum c_j x_j = K;$ $c_j, K$ -- целые) и 0-1 рюкзак (так же, но $x_j \in \{0,1\}$). Свести к этим задачам как-то не получается, как же быть?

Где, быть может, можно прочитать, конкретно об NP-трудности именно этой задачи?

[_hum_]

Как-то намешано в вопросе все в кучу... Какую именно задачу к какой хотелось бы свести?
- "максимизировать" к "существует ли"
- "произвольные коэффициенты $w_j$" к "целым $c_j$"
- "$= K$ " к "$\leqslant K$"
?

По поводу литературы, возможно, имеет смысл глянуть "Босс В. Лекции по математике т.10 Перебор и эффективные алгоритмы "

[max(Im)]

Ну почему же в кучу...
Вопрос - как доказать NP-трудность задаче о рюкзаке в общей (приведенной в начале первого сообщения) формулировке?

При этом есть знания о том, что задачи о целочисленном рюкзаке и о 0-1 рюкзаке NP-полны как задачи распознавания. Если это не поможет, надо что-то еще...

[_hum_]

Может, я чего не понимаю, но в чем тогда проблема? Считаем, что ваша задача

max(Im) в сообщении #780441 писал(а):

максимизировать $\sum c_j x_j$ по целым $x_j$ при условии $\sum w_jx_j \leqslant K$ (суммы от 1 до $n$)

полиномиально разрешима. Тогда, рассматривая ее частный случай $w_j = c_j$, получаем полиномиальную разрешимость задачи

$$\sum c_i x_i \rightarrow \max, \quad \sum c_i x_i \leqslant K, $$

применяя которую, легко решить задачу распознавания существования решения уравнения $\sum c_i x_i = K$ (для этого достаточно сравнить найденный максимум с числом $K$). Ну, а это будет означать полиномиальную разрешимость задачи распознавания для рюкзака, как вы и хотели

max(Im) в сообщении #780441 писал(а):

Обычно NP-трудность некоторой задачи $A$ доказывают построением полиномиального алгоритма для какой-нибудь NP-полной задачи в предположении существования полиномиального алгоритма для $A.$