“Make it work, make it right, make it fast.” — Kent Beck
Hey there! Hope you all must have enjoyed the previous blog in which we solved the Frog Jump problem from AtCoder. We have a lot of amazing problems for the upcoming blogs but this one is going to be an important starter problem for any newbie in the world of competitive coding or an interview aspirant who wants to learn DP.
Let’s start with the discussion
Today we will be solving an orthodox DP beginner level problem — “Knapsack Problem”. It involves a very important technique i.e. take it or leave it.
The problem statement is as follows — There are N items numbered 1,2,3…N. Each item ‘i’ has a weight of wt_i and a profit-value of profit_i associated with it. You have a bag ( or you can say a Knapsack ) whose maximum weight capacity is W, which means that the sum of the weights of items taken must be at most W. Find the maximum possible profit you can get by choosing some items. ( 1 ≤ n ≤ 100, 1 ≤ W ≤ 10⁵ )
You can read the problem statement from here.
Let’s start solving
STEP 1 — Build a naive recursive solution
We would be making a simple recursive function that would be keeping track of the total profit earned so far. Suppose we are at index i, we have exactly 2 options, either put the item at this index in our knapsack or leave it.
- If you choose to put the i’th item in your knapsack, you have to make 2 changes. First of all, our existing profit value would be increased by the profit associated with the current item, and secondly, our maximum permissible weight for further computations would be decreased by the weight of the current item.
It means if are at index idx and have taken the item at this index, new profit value would become profit_so_far+profit[idx] and our new maximum permissible would become max_weight_capacity — weight[idx].
- If you choose to leave the current item the value of profit_so_far and max_weight_capacity would remain unchanged and we move to the next index.
At last we have to consider the maximum value yielded from each of the above two decisions.
The above recursive solution would have 2 base conditions:
- If max_weight_capacity for the current function call is less than 0 ( i.e. we earlier took an item whose inclusion exceeds the maximum weight capacity) we return a very small value ( -10¹⁶ approx.). The purpose of returning a very small value is that we want to ignore the current case and since we want to get the maximum profit we can neglect small profit values.
- We have finally considered all the cases and have reached the n’th index. Simply return 0.
Let’s look at the recursive code from the above discussions
Time Complexity — O( 2^n ) ( as in every step we have 2 choices, take the item or leave it. Thus by basic P&C we can very easily prove that the total number of ways will be 2^n ).
STEP 2 — Memoize the recursive solution
We can see that in the above code the parameters that are changing in every function call are: idx and max_weight_capacity.
So if we keep a track of profit for each value of idx and max_weight_capacity we would be solving the problem.
We know that the value of idx ranges from 0 to 99 and that of max_weight_capacity ranges from 0 to 10⁵. So in order to keep track of all index and capacity values, we have to make a 2-D DP matrix of size 100 x 10⁵ and we are done.
Here is the memoized code
Time Complexity — O( N*W ).
To check your understandings you can try submitting your code here.
I know this blog is a bit long, but the technique discussed in this problem would surely help you understand tougher DP problems efficiently. Just stay tuned with this DP series you might learn something new with each blog.
For any doubts in the above explanations, you can mail me at — ankitpandeycu@gmail.com
Share this blog with your peers if you find it useful.
Hope it helps.
AnkitCode99 here….
