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]