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]], необходимо доказать два факта:
*Если исходная [[NP-полнота задачи о сумме подмножества|задача о сумме подмножества]] имела решение <math>S'</math>, то набор пар <math>P'</math> с весами, равными числам из <math>S'</math>, будет решением задачи о рюкзаке.
*В обратную сторону - аналогично.
[[Категория:NP]]
