You are not logged in. Please login at to post your questions!


Doubt in concept of Knapsnack

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

sreyan32's gravatar image

accept rate: 0%

converted to question 12 Dec '17, 16:29

vijju123's gravatar image

4★vijju123 ♦♦

For negative weights you can use the meet in middle approach as explained by @gkcs here:- 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

vishesh_345's gravatar image

accept rate: 8%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 12 Dec '17, 14:33

question was seen: 313 times

last updated: 14 Dec '17, 15:12