There are no over lapping sub problems in this question(Knapsak 01)

#1

Please tell me hw to apprach this question through DP

#2

Hey @KetanPandey
There will be overlapping subproblems in case of duplicates or say we have 1 2 5 4… here we take 1,5 wts in one set and 2,4 wts in other set till i=4 then remaining Wt is same W-6 so here its again overlapping .

Approach:
if u have any further doubt regarding this then don’t hesitate to ask.

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.

#3

Ok , i got this approach,can you elaborately explain me (like you did in my last question) the time complexity difference btw dp approach and recursive approach.Thanks…

#4

Dont you think if the value of S(total weight) is small,recursive approach will have less complexity than dp approach

#5

Hey @KetanPandey

Time compexity for recursive approach is 2^n
Because we will either take some item or leave it
And Time complexity of dp approach is nW because of nested loops

#6

Hey,i made the code using top down approach but it is printing some garbage value.Please correct the code and tell me my error.link:https://ide.codingblocks.com/s/333872

#7

Hey @KetanPandey
Problem is on line 13,it should be

cin>>value[i];

Also set ur dp array size as 1001*1001

#8

Hey @KetanPandey
If ita resolved then please mark it so :slight_smile:

#9

Thanks …

1 Like