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. asked 12 Dec '17, 14:33
converted to question 12 Dec '17, 16:29

For negative weights you can use the meet in middle approach as explained by @gkcs here: https://www.youtube.com/watch?v=57SUNQL4JFA Because a DP solution requires w to be kept in an array. Although it might be possible to do it with that. I have a doubt in this video. Why we have not considered the two weights of same set. Each weight of one set 1 is used to determine the upperbound in set 2. But why not weights of same set. Thanks in advance. answered 14 Dec '17, 15:12
