Done approach with 2D array as recursive storage. All testcases passed.
But I want to know the iterative approach for this problem as sir solved these type of questions using iterative approach.
0-1 Knapsack problem
it is very difficult to express the approach on computer.
i found this in the solution section and the explanation is fine.
so i just copy paseted it.
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.
The explanation you gave involves recursion or not?
also I’m not able to understand this explanation.
this solution is based on DP.
do you know the target subset problem using dp?
DP is ok. Is this recursive dp or iterative dp?
Tell me about target subset problem. Didn’t listened about it.
This is basically a very impt dp. Problem.
Aapne dp kiya hai
May you please mention where it is in the course. Maybe I would have done it but with different question name.
Have u heard about dynamic programming
Yes and completed its videos section. Don’t say like that. Done about 3-4 challenges of DP too.
Sorry, bro
Is target subset is not there in the DP section?
0 1 knapsack also should be in dp section
Are you talking about this question?
Its given in the middle of Challenges thats why I haven’t heard
Yup,
A set is given 2 you and target
You have to tell that, a subset can be formed whose sum is equal to target.
Pls do all the qns of dp.
DP is d most important topic for the placements,.