How is the subset sum problem a special case of the knapsack problem ? Does the knapsack problem allow negative weights ?
If the set is only consisting of positive numbers for example -: {7, 3, 5}, and the target sum is 10 I can model this as a knapsack problem if I take the weight of the knapsack to be the target sum as the max weight of the knapsack and the value of each number to be the weight of each item. The value of each item would have to set to a constant value that is same for each item.
But this logic only works for positive numbers. How would I model the problem of {-7, -3, 5} and the target sum to be -10, as a knapsack problem ?
How would you construct the DP table in this case ? What would be the base condition ? What would be the initial weight of the knapsack ?
I am following this tutorial for constructing the DP table for 0/1 Knapsack problem.