I want to prove that the subset sum problem is polynomially reducible to the Knapsack problem.
Overall I want to show that Knapsack is NP-complete.
There are two parts to showing knapsack is NP-complete
- knapsack is in NP
- If I show that the subset sum problem is polynomially reducible to the knapsack.
Then since subset sum problem is known to be NP-hard. Knapsack is NP-Hard
Both 1) and 2) imply that Knapsack is NP-Complete
- Is trivial as given any sequence of items we can verify the sum of their value
and weights in linear time. So the knapsack is in NP. Correct me If I am wrong here.
How do I approach 2)? I am not sure how to phrase the polynomial conversion
from the subset sum problem to the knapsack.