You are not logged in. Please login at www.codechef.com 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

0★sreyan32
112
accept rate: 0%

converted to question 12 Dec '17, 16:29

vijju123's gravatar image

5★vijju123 ♦
13.9k11241


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.

link

answered 14 Dec '17, 15:12

vishesh_345's gravatar image

1★vishesh_345
2567
accept rate: 8%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×1,810
×283
×1

question asked: 12 Dec '17, 14:33

question was seen: 274 times

last updated: 14 Dec '17, 15:12