1632
правки
Изменения
м
rollbackEdits.php mass rollback
<p style="text-align:center;">
<math>\exist exists P' \subseteq P: ((\sum_{(w_{i},v_{i}) \in P'}{v_{i}} \geq p) \wedge (\sum_{(w_{i},v_{i}) \in P'}{w_{i}} \leq c))</math>
</p>
==Доказательство NP-полноты==
Для доказательства того, что Knapsack problem <math>\in</math> [[NPC]], необходимо доказать два факта:
<p style="text-align:center;">
<math>f(S,s) = ((S,S),s,s) \,</math>,
</p>
То есть, для каждого числа <math>q \in S</math> создадим предмет <math>(q,q)</math> с весом и стоимостью, равными значению числа <math>q</math>.
А значения <math>c</math> и <math>p</math> возьмем равными <math>s</math>.
*Очевидно, <math>f~</math> работает за полиномиальное от длины входа время.
*Если исходная [[NP-полнота задачи о сумме подмножества|задача о сумме подмножества]] имела решение <math>S'</math>, то набор пар <math>P'</math> с весами, равными числам из <math>S'</math>, будет решением задачи о рюкзаке.
*В обратную сторону - аналогично.
[[Категория:NP]]
