0-1 knapsack problem

#1


bhaiya dhkna ek baar
answer thik nhi aara

#2

Here the state of any subproblem can be defined by using 2 variables i.e id and remW where id is the index of the current item to be considered and remW is the remaining weight left in the knapsack.
knapsack(id, 0) = 0 // if remaining weight is 0, we can’t take anything .
knapsack(n, remW) = 0 // if id = n we have considered all the items .
if(W[id] > remW), we have no choice but to ignore this item .
if(W[id]≤ remW), we have two choices either we can ignore this item or include it .
Value1 = knapsack(id+1, remW) // Not including .
Value2 = knapsack(id+1, remW - W[id]) // Included .
knapsack(id, remW) = max(Value1. Value2 + V[id]) .
Example: n = 3, V = {60,100,120, 80}, W = {100,40,60,120}, S = 120.
Here we can easily see some overlapping subproblems. After including the 0th item and ignoring 1st and 2nd item we arrive at state knapsack(3, 20) i.e. at the third item with 20 units weight left. Also if we ignore the 0th item and include both the 1st and the 2nd item we arrive at the same state i.e. knapsack(3, 20). So here we got an overlapping subproblem. The total number of possible states for this knapsack problem can be O(nS) where n is the number of items and S is the maximum weight possible.
see this