11.23

1  Membership in NP
Given a candidate subset S′ we can in O(n) time add its weights and values and check
[math]\displaystyle{\sum_{i\in S'}w_i\le W\ \text{and}\ \sum_{i\in S'}v_i\ge V}. [/math]
Because the numbers are written in binary the sums have at most polynomial length, so the verifier is polynomial. Hence Knapsack ∈ NP.

2  NP–hardness by reduction from PARTITION
PARTITION (known NP-complete) : “Given integers a₁,…,a_n with total [math]2B=\sum a_i,[/math] does a subset sum exactly to [math]B[/math]?”

Transformation (polynomial): for every a_i create a knapsack item with [math]w_i=v_i=a_i.[/math] Set the knapsack parameters
[math]W=B,\qquad V=B.[/math]

• If the PARTITION instance is YES, a subset with [math]\sum a_i=B[/math] exists. In the knapsack it satisfies [math]\sum w_i=B\le W\quad\text{and}\quad\sum v_i=B\ge V,[/math] so the knapsack answer is YES.
• Conversely, any YES subset of the knapsack has identical weight and value, therefore [math]\sum w_i=\sum v_i\ge V=B.[/math] But we also have [math]\sum w_i\le W=B,[/math] hence the sum equals exactly [math]B,[/math] yielding a YES subset for PARTITION.

Because the mapping keeps item count and encodes only the same numbers, it is computable in time O(n). Thus PARTITION ≤_P KNAPSACK, so KNAPSACK is NP-hard.

3  Conclusion
KNAPSACK is in NP and NP-hard, therefore it is NP-complete. ∎

Back to Chapter 11