Knapsack problem

Page 1 of 1

1 Replies - 817 Views - Last Post: 01 June 2016 - 10:17 PM

#1 echo75

Reputation: 0
• Posts: 9
• Joined: 21-May 16

Knapsack problem

Posted 01 June 2016 - 09:33 PM

I have a question with the 0/1/2/3 knapsack variation of 0/1 problem. Unlike 0/1 Knapsack problem which you can pick either 0 or 1
copy of the object, 0/1/2/3 Knapsack Problem allows to pick either 0 or 1 or 2 or 3 (that is, we assume that 3 copies of each object are available).

I know for 0/1 knapsack problem functional equation for dynamic solution is f(X) = max( p + f(X-w), f(X) ) for X > w (where X is max capacity p is profit and w is object weight). How would i modify the equation to solve 0/1/2/3 knapsack problem? Is it just 2 other terms in the equation with times 2 and times 3?

Is This A Good Question/Topic? 0

Replies To: Knapsack problem

#2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12135
• Posts: 45,119
• Joined: 27-December 08

Re: Knapsack problem

Posted 01 June 2016 - 10:17 PM

That's the general idea. Of course, you have to consider:

max \{ p_{i} + f(X - w_{i}) : i \in O \} U { f(X) }

Where O is your set of objects. That is, make sure to consider each object in the maximization problem. Your notation is not indicative that you are considering this (and is something folks teaching theory classes tend to be picky about).