So far, we have discussed the recursive approach for solving the zero one knapsack problem, and we
have also seen that the solution that we came up with had an O of two to the power n time complexity,
and an O of n space complexity.
Let's now proceed with the memoization or top down approach for solving the knapsack problem, and we
will see that by just adding a few lines of code, we will be able to convert the recursive approach
to the memoization approach.
So let's get started for discussing the memoization approach.
Let me again take an example.
Let's take the case where we are given three items and the capacity of the knapsack is eight units.
We have previously seen that the recursion tree for this would look something like this.
So let's say we are starting from the last index and we are going till the first index over here.
So initially we are considering item three and we have two choices.
We can either include item three or we can exclude item three.
And then in this manner we proceed down the recursion tree.
Now let's take a look at how we can memorize this.
For this we will need a table.
And the number of rows is going to be equal to the number of items that we have.
And the number of columns is going to be equal to one plus the weight limit.
So over here the weight limit was eight.
So we are going to go from zero up to eight.
So we have the weights over here and the items over here.
And this is the dynamic programming table that we will be using.
We can also call it the memoization table.
Now initially we will fill all the cells with the value minus one.
Now it's important to understand what a cell represents.
So let's take this cell over here.
Now this represents the subproblem where the remaining weight that can be added to the knapsack is equal
to this weight over here, which is four.
And the items that are available are these items over here which is i2 and i1.
So that's this subproblem over here.
Now what would be this subproblem over here.
This subproblem would indicate that the remaining weight that can be added is seven.
And the items that can be considered are I3, I2 and i1 or the three items that we have.
And again finally this cell over here would indicate the remaining weight that can be added to the knapsack
is equal to eight.
And the items that we have are I3, I2 and i1.
And whatever we will be filling in this cell would actually give us the answer, because you can see
that this is the original problem which was asked of us.
Now let's just quickly walk through the recursion tree and let's see how values will be filled in the
dynamic programming table over here.
So in this approach we are going from i3 to I1.
So initially we are over here we have two choices whether to include i3 or exclude i3.
Let's say we have written the code in such a manner that include happens before exclude.
So the algorithm would go down this branch and it has included i3.
And let's say it sees that item two also can be included because the remaining weight that can be included
is three.
And the weight of item two is just two.
So the algorithm goes over here.
And then we are considering item one.
And item one has a weight of eight.
And the remaining weight that can be included is one.
So we don't have an include branch.
So we set this to zero okay.
And in over here we have the exclude branch.
And when we come to the exclude branch the remaining weight that can be added is still one.
But then we are not adding anything.
So the value over here is zero as well.
So we have the value zero over here and the value zero over here.
So the maximum of these two values is zero itself.
So this problem over here which is you have just item one.
And the remaining weight to be filled is one.
So this subproblem is going to have a value zero.
And in the memoization approach we are going to store this.
So the items that can be considered are just item one.
So that's this row over here.
And the remaining weight that can be added is equal to one.
So that's this column over here.
So we will be filling this cell over here with the value zero.
So let's do that.
So next time, let's say if we do encounter this sub problem, then we would not be computing it, but
we would just retrieve what we have stored and we would return it.
Now let's proceed.
So the algorithm has found this answer.
Then it comes down this branch.
So over here we are just left with item one and weight three.
We can't include it because item one has a weight of eight.
So this over here becomes zero.
And then if you exclude it the value is still zero.
And the remaining weight that can be added is three.
So you have zero over here and zero over here.
So this subproblem over here also becomes zero right.
So you come over here and this is also zero.
The maximum between 0 and 0 is zero itself.
So the subproblem where you can only consider item one and the remaining weight is three.
So this subproblem over here becomes also zero.
And we can store it in the memoization table.
So we can only consider item one.
And the remaining weight is three.
So we store zero over here.
Again this is also zero.
This is also zero.
And over here we have to add value two to this.
So value two is three.
So three plus zero becomes three.
So this over here has returned three.
And this would be returning zero.
So the maximum between 3 and 0 is three.
So that's why this subproblem over here where you have item two and one and the remaining weight to
be added is three.
So that's this cell over here becomes equal to three.
And we fill it in the memoization table.
Let's proceed.
So this branch over here returns the value three plus value three value three is nine.
So three plus nine is 12.
So this returns 12.
And then the algorithm comes down this path.
All right.
So we come over here.
Then we would come over here and then we would come over here.
And over here we are not able to include.
So the value is zero.
And when we exclude again we get the value zero.
The maximum between 0 and 0 is zero itself.
So this subproblem over here where you only have item one and the remaining weight to be added is six.
So that's this cell over here that also becomes zero.
So we add that over here.
And then we return over here.
Value two plus zero.
Value two is three.
So three plus zero three is getting returned over here.
Then we come down over here and then we come over here where we are able to include item one, because
you can see that the remaining weight to be added is eight and the weight of item one is eight itself.
So we are able to include this.
So when we do include it we get the value two back over here.
And over here.
When we exclude, we get back the value zero.
So the maximum between 2 and 0 is two.
So the value of this subproblem over here where you just have item one and the remaining weight to be
added is equal to eight.
So this subproblem over here becomes two.
So we can store two over here.
So let's do that.
All right, so we get three over here and over here.
This part over here returns two.
So the maximum between 3 and 2 is going to be equal to three.
So this subproblem over here where you have item two and item one.
So that's this row over here.
And the remaining weight to be added is eight.
So that's this column.
So this cell over here is going to take the value three.
So we store that over here.
And this returns three.
And then the maximum between 3 and 12 is 12.
So the problem where we have all the three items, that's this row.
And the remaining wait to be added is eight.
That's this column will have the value 12 because 12 is the maximum between 12 and 3.
And we store that over here.
So let's do that.
And this is the answer to the problem at hand.
So this is the memoization approach for solving the zero one knapsack problem.