18
правок
Изменения
Доказательство закончено
==Формулировка задачи==
В '''Задаче о рюкзаке''' (Knapsack problem) входными данными являются набор <math>n</math> пар целых чисел <math>\{w_{i}\}</math> - вес и <math>\{v_{i}\}</math> - стоимость, а также два целых числа <math>c</math> - максимальный вес и <math>p</math> - минимальная стоимость. Требуется определить, можно ли выбрать такое подмножество пар, что их суммарная стоимость больше либо равна <math>p</math>, а вес меньше или равен <math>c</math>:
<p style="text-align:center;">
<math>\exist \{k_{j}\} \subseteq (1..n): (\sum_{i \in k_{j}}{v_{i}} \geq p) \wedge (\sum_{i \in k_{j}}{w_{i}} \leq c)</math>
</p>
==Доказательство NP-полноты==
Для доказательства того, что <math>Knapsack~ problem \in NPC</math> необходимо доказать два факта:
*<math>Knapsack~ problem \in</math> [[NP|<math>NP</math>]]
*<math>Knapsack~ problem \in</math> [[NPH|<math>NPH</math>]]
===Доказательство принадлежности к NP===
В качестве сертификата возьмем удовлетворяющее условию задачи подмножество пар <math>\{k_{j}\}</math>. Очевидно, оно удовлетворяет всем требованиям,
налагаемым на сертификат.
===Доказательство принадлежности к NPH===
Сведем [[NP-полнота задачи о сумме подмножества|задачу о сумме подмножества]] к задаче о рюкзаке. Пусть <math>f\!\!:(\{s_{i}\},s) \to (\{w_{i}\},\{v_{i}\},c,p)</math> - функция, осуществляющее сведение. Она будет устроена так:
<p style="text-align:center;">
<math>f(\{s_{i}\},s) = (\{s_{i}\},\{s_{i}\},s,s)</math>
</p>
Очевидно, <math>f</math> работает за полиномиальное от длины входа время. И удовлетворяет условиям [[Сводимость по Карпу|сводимости по Карпу]].
