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

Формулировка задачи

В Задаче о рюкзаке (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]:

[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]

Доказательство NP-полноты

Для доказательства того, что [math]Knapsack~ problem \in NPC[/math] необходимо доказать два факта:

• [math]Knapsack~ problem \in[/math] [math]NP[/math]
• [math]Knapsack~ problem \in[/math] [math]NPH[/math]

Доказательство принадлежности к NP

В качестве сертификата возьмем удовлетворяющее условию задачи подмножество пар [math]\{k_{j}\}[/math]. Очевидно, оно удовлетворяет всем требованиям, налагаемым на сертификат.

Доказательство принадлежности к NPH

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

[math]f(\{s_{i}\},s) = (\{s_{i}\},\{s_{i}\},s,s)[/math]

Очевидно, [math]f[/math] работает за полиномиальное от длины входа время. И удовлетворяет условиям сводимости по Карпу.