We have discussed the recursive approach and the memoization approach, and for the memoization approach,
the time and space complexity were of the order of n into W.
Now let's get started with the bottom up or tabulation approach for solving the zero one knapsack problem.
Now again for this, let's take the same example where we are given three items and the maximum capacity
of the knapsack is eight units.
Now over here we will again need a DP table.
Now let's draw that over here.
So I have in this case four rows even though I just have three items.
And again I have columns over here which go from zero up to eight.
Now this is similar to the memoization table.
Now you could have an extra row as you have over here in the case of memoization as well.
But then that's not needed over there.
And that's why I've not included it there.
But in the tabulation approach, it's very helpful to have this row over here, because as you will
see, we will be using values from a previous row to fill values in the next row.
So this row over here, which indicates not having any item, is useful for setting the initial conditions,
which can be used for filling the next row over here.
So let's just have this over here.
And once we do a dry run the utility of this will become very clear.
So let's get started.
Now we had previously discussed that in the tabulation or bottom up approach, the initial conditions
will be similar to the base case that you have in the recursive approach.
The base case in the recursive approach was indicative of let's say the remaining weight is zero.
In that case we would return zero, or if there is no valid item, we would return zero.
So again this is the initial condition for the tabulation approach.
So if W is zero which indicates this column then the value is going to be zero.
Or if n is equal to zero, or if there are no items which is indicated by this row, the values are
going to be zero.
So we're going to fill this row over here and this column over here with the value zero.
So let's do that.
All right.
Notice over here that there is no need to initialize values, as we had done in the case of memoization.
In the case of memoization, we had filled each of these cells with the value minus one.
And we use that to understand whether we had already computed a value or whether we had to go ahead
and compute it.
But over here we don't need that because we will be going row by row, which means that first we will
fill this cell.
Then we will proceed and fill this cell.
And in this manner we will go through each cell over here till finally we come over here.
And this is where we will get the answer.
Now let's discuss how to find the value of a particular cell.
Now let's call this table depee.
And if the rows over here are indicated by I, and if the columns over here are indicated by J, then
we can denote the value of a cell as depee at I and j.
Now how do we calculate this value?
Now it's going to have the same logic as for the recursive approach.
So we have an option to exclude the item at hand which would be depee at I minus one j.
And again j is the weight.
So when you exclude an item, notice that the remaining weight that can be added to the knapsack remains
the same.
So over here also you have J.
And over here also you have J.
But then you have one item less which is what you are doing over here when you're saying I minus one.
So that's the exclude case where the same weight can still be added to the knapsack.
But you have one item less so exclude is equal to dp at I minus one j.
And then you have to compute the include case for include.
Also you would have one item less, but the value has to be changed because you have included an item,
and the remaining weight that can be added to the knapsack has to be reduced.
So include is going to equal value at I minus one plus dp at I minus one, and j minus weight at I minus
one.
Now over here notice that we have said value at I minus one, even though we included the value that
we were considering.
Now why is that?
So let's try to understand that now.
For example, let's say we are filling this cell over here.
So when we are trying to fill this cell and when we are calculating the include value, and when we
say that value at I minus one, what we want to achieve is we want to add the value of the first item.
Now notice that the value array and the weight array are zero indexed, and the index of the first item
is going to be zero.
But over here we are talking about item one, because we have already filled the value over here as
zero for the case where we are not taking any item, and then we have the cases of item one, item one
and two, and item three up to one.
Right.
So over here I is going to take the value one in the DP array.
But it's indicative of the first item.
And because the value and weight array are zero indexed.
That's why over here we have to do I minus one.
And again it's the same logic for weight of I minus one over here as well, because we want to subtract
the weight of the included item from the remaining weight that can be added to the knapsack.
So we have understood why we have value at I minus one over here and weight at I minus one over here.
But over here we have DP at I minus one because we have added the item and we just have one item less.
So the reason for I minus one over here and here is different for the I minus one over here.
Now again notice over here also we had DP at I minus one j.
That was because we wanted one item less and we wanted to go one row above in the DP table, which is
what we have over here.
So whenever you are dealing with an item in the ith row in the DP array, to convert an identify that
item's value and weight, you have to do I minus one, which is what we have done over here and over
here.
All right.
So we have found the remaining weight over here.
And we are going one row up because we want to think of the remaining items that we have.
All right.
So we have seen what exclude is and we have seen what include is.
Now let's just walk through and see how the algorithm would fill this table.
So the first cell that we are trying to fill is this one over here where we have just item one.
And the remaining weight that can be added is one.
Now there are two possibilities exclude and include.
Now exclude is having no item because we are excluding this item and we just had one item to start with.
So when we exclude this we have no item.
So that's dp I minus one.
So we are coming to this row where we don't have any item and the remaining weight stays the same which
is one itself.
So notice that this zero gives us the value of dp I minus one j.
So that's the exclude value.
And then when we are trying the include case notice over here the weight of the first item is eight
and the remaining weight that we have at this point that can be added to the knapsack is just one.
So we are not able to include this item.
So in.
Load is also set to zero, so exclude is zero and include is zero.
So the maximum between these two is zero itself.
And thus we can fill over here zero.
Now in a similar manner.
You will see that over here also, because the weight of the first item is eight, we will not be able
to include it in any of these cases, because the weight of this item is not less than or equal to any
of these weights.
So for all these cases include is going to be equal to zero and exclude as we have seen is just depee
I minus one j, which is the value that we have in the previous row.
So for this cell the exclude value is this.
For this cell the exclude value is this.
And it goes on in this manner.
So include is zero for all of these.
And exclude is also zero for all of these.
Therefore we can just fill zero in all these places.
Now when we come to this cell over here.
Notice that again, exclude is still zero.
That's the value that we have over here.
And we are able to include the item at hand because the weight of the item one is eight, and the remaining
weight that can be added over here is also eight.
So the value of include over here becomes value at I minus one I is equal to one.
So over here I is equal to one.
So value at I minus one is value at one minus one, which is value at zero.
And this is index zero right.
So value at zero is two.
So this becomes two.
And then we have dp at I minus one which is this row over here.
And j minus weighted I minus one.
Now weight at I minus one has to be subtracted from j.
So j over here is eight.
So let's write that over here.
And weight at I minus one is weight at zero which is this eight itself.
So we get eight minus eight over here.
And over here I minus one is one minus one which is zero.
So this term over here becomes DP at zero zero which is zero itself.
So include becomes two plus DP at zero zero which is two plus zero okay.
So we have exclude as zero.
This is exclude.
And include is two plus zero, which is two, and the maximum between 0 and 2 is two.
So we fill two over here.
And we're done with this row.
Now let's proceed to the next row, and let's fill this cell over here.
Again notice the exclude value is just going to be this value over here.
All right.
So for this cell exclude is going to be this value over here.
And can we include this value.
So let's take a look at that.
So the weight that can be added at this point is one.
And the weight of item two is two.
So we cannot add it.
And therefore include is also zero.
And therefore the maximum between 0 and 0 is just zero.
Now what about the next cell over here.
Again exclude is going to be zero.
But what about include.
Now the weight of item two is two and the remaining weight that can be added is also equal to two.
So we can include this item.
And if we do include it we are going to get this value.
Because over here.
I is going to be equal to two.
So value at two minus one is value at one, which is this value which is three.
So we get value of three over here.
And dp at I minus one is the previous row okay.
So two minus one is one.
So this is going to be equal to one.
And then we have j which is two minus wait at this index over here which is one because over here I
is two right.
So wait at two minus one is wait at one which is two.
So we have two minus two over here.
So include is going to be three plus depee at one and then two minus two which is zero.
So DP at one.
That's this row over here at index zero is zero itself.
So this is three plus zero which is three.
So maximum between 0 and 3 is three.
So we can fill over here three.
Now let's proceed to the next cell.
Again.
Exclude is going to be equal to zero and include at this point is going to be three plus because the
value of item two is three we have seen that.
So it's going to be three plus depee at one which is the previous row.
And then you have three which is this three over here minus the weight of the item that's included which
is two.
So you get DP at one comma one okay.
So that's this value over here which is zero itself.
And the maximum between 0 and 3 is three.
So we fill three over here.
Let's proceed to the next cell.
And again over here you can see that exclude is again zero.
But when it comes to include you have three plus depee at one.
And then you have this four minus two and DP at one and four minus two which is two.
Is this zero itself.
So over here of zero and you have three.
And the maximum between these two is three.
So we fill three over here we proceed to the next cell.
Again exclude is zero and include is going to be three plus depee at one and then five minus two.
And over here that's three and DP at one and three.
Is this cell over here which is again zero.
So between 0 and 3 the maximum is three.
So we fill three over here we proceed to the next cell.
And over here again exclude is zero.
And you will see that include is three.
And therefore we can fill three.
Over here we proceed to the next cell.
Over here again exclude is zero and include is going to be three.
So we can fill that over here.
So we get three again over here.
And finally we come to this cell over here again.
Exclude at this point is going to be equal to two and include is going to be three plus depee at one
and eight minus two.
Because this is eight and from eight you have to subtract two.
So dp at one six.
Is again zero.
So over here you have two.
And over here you have three.
And the maximum between these two is three.
So that's why you can fill three over here as well.
And we're done with the second row.
Now let's proceed to the next row again for this cell exclude is going to be equal to zero.
And include is also going to be equal to zero.
Because we will not be able to include item three because its weight is five.
And the remaining weight that can be added is only one.
So for all these values one up to four, we will not be able to include that item and we can just fill
the value from exclude, which is what we have over here.
So we can say zero, three, three and three over here.
Now when we come over here, exclude is going to be the value three and include is going to be equal
to this nine over here plus depee at two.
And then wait is five this five minus wait at two, which is the weight of this item which is five.
So that's five minus five.
So DP at two and then zero.
That's this value over here which is zero itself.
So you have exclude to be three and include is nine.
And the maximum between 3 and 9 is nine.
So we will fill nine over here.
Now let's proceed to the next cell.
Now over here again exclude is going to be equal to three.
And include is going to be equal to nine plus DP at two.
And then you have six minus five six minus five is one.
So DP at two and one is again zero.
So this term over here becomes zero.
And then you have three and nine over here.
And the maximum between these two is nine.
So we feel nine over here.
We proceed to the next cell.
Again exclude is going to be equal to three.
And include is going to be equal to nine plus depee at two.
And then you have seven minus five over here because you have seven over here.
So that's this seven.
And then over here you have five.
Now DP at two two is this value over here which is three.
So you have nine plus three over here which is 12.
So the maximum between 3 and 12 is 12.
So we will fill 12 over here.
Now let's proceed to the next cell.
Now for this exclude will have the value three and include is going to have the value nine plus depee
at two.
And then you have over here eight minus five.
Because five is this weight over here.
Now eight minus five is three.
So deep at two and three is this value over here which is three.
So nine plus three gives you 12.
So you have three and 12.
And the maximum between 3 and 12 is 12.
So we fill 12 over here.
And this is going to give us the answer.
So the answer to this question is 12 which is the value in the DP table at index n w.
So this is row n.
And over here you have column w.
So dp at n w gives us the answer.
So this is the tabulation approach for solving the zero one knapsack problem.