Изменения

Перейти к: навигация, поиск

NP-полнота задачи о рюкзаке

4 байта добавлено, 16:20, 3 мая 2016
syntax error fix in Формулировка задачи
<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]], необходимо доказать два факта:
Анонимный участник

Навигация