Изменения

В '''Задаче задаче о рюкзаке''' (Knapsack problem) входными данными являются набор <math>n</math> пар целых чисел <math>P = \{(w_{i},v_{i})\}^{n}_{i=1}</math>, где <math>w_{i}</math> - вес и i-го предмета, а <math>\{v_{i}\}</math> - стоимость, а и также два целых числа <math>c</math> - максимальный вес и <math>p</math> - минимальная стоимость. Требуется определить, можно ли выбрать такое подмножество партакой набор предметов, что их суммарная стоимость больше либо равна <math>p</math>, а вес меньше или равен <math>c</math>:

<math>\exist \{k_{j}\} P' \subseteq (1..n)P: (\sum_{(w_{i},v_{i }) \in k_{j}P'}{v_{i}} \geq p) \wedge (\sum_{(w_{i},v_{i }) \in k_{j}P'}{w_{i}} \leq c)</math>

Для доказательства того, что Knapsack problem <math>\mbox{Knapsack problem} \in NPC</math> [[NPC]], необходимо доказать два факта:*Knapsack problem <math>\mbox{Knapsack problem} \in</math> [[NP|<math>NP</math>]] *Knapsack problem <math>\mbox{Knapsack problem} \in</math> [[NPH|<math>NPH</math>]]

В качестве сертификата возьмем удовлетворяющее условию задачи подмножество пар <math>\{k_{j}\}P'</math> с суммарным весом, не большим <math>c</math> и стоимостью не меньше <math>p</math>. Очевидно, оно удовлетворяет всем требованиям,налагаемым на сертификат. Проверяющая функция строится очевидным образом и работает за полиномиальное от размера входа время.

Сведем [[NP-полнота задачи о сумме подмножества|задачу о сумме подмножества]] к задаче о рюкзаке. Пусть <math>f\!\!:(\{s_{i}\}S,s) \to (\{w_{i}\},\{v_{i}\}P,c,p)</math> - функция, осуществляющее сведение. Она будет устроена так:

<math>f(\{s_{i}\}S,s) = (\{s_{i}\}(S,\{s_{i}\}S),s,s) \,</math>

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