Problem Statement :
There are N items, numbered 1,2,…,N. For each i (1≤i≤N), Item i has a weight of W_{i} and a value of V_{i}.
We have to choose some items among them so that total weight of the taken items in knapsack should not exceed W.
N and W will be given to us.
Find the maximum possible sum of values of items without violating the conditions mentioned above.
Naive Approach :
· We can take each subset and then we can check whether the given conditions satisfy or not.
· If a subset satisfies the given conditions, then we may update the maximum value, depending upon the total value of the items included.
Time Complexity :
· In each step, we have 2 options either to take the item or not.
· We can do better than that using the same approach. Let’s see how!!
Optimisation :
· We just have to store the previously calculated values so that we need not to calculate the same values again and again.
· Suppose I am starting from index 0 and as mentioned in the problem I can take atmost W weight.
· Now I am at index 0 and I have two options : either to take the item or not. If take the item then I can take atmost W-w[0] in the knapsack.
· If I don’t take the item, then I can still take atmost W weight in the knapsack.
DP State : dp[x][y] where, x refers to the starting x items considered till now and y refers to the maximum weight capacity that knapsack can still have after considering first x items.
Recursive Condition : The maximum value that can be obtained from ‘n’ items is the max of the following two values :
1. Maximum value obtained by n-1 items and weight W (excluding nth item).
2. Value of nth item plus maximum value obtained by n-1 items and W minus the weight of the nth item (including nth element).
Base Case : When number of items included is 0 then the value should be 0 or when the weight remaining is zero then also value should be 0.
Edge Test Case : When weight of nth item is more than ‘W’ then we cannot include it in our knapsack and hence we are left with only Case 1 ,i.e, to exclude the nth item .
Time Complexity :
Code :
Input format :
N W
W_{1} V_{1}_{}
W_{2} V_{2}_{}
…….
W_{n} V_{n}_{}
Code:
Happy Coding 😊
By Programmers Army
Contributed by Shubham Kumar