Let's now write the tabulation approach for solving the zero one knapsack problem.
Okay.
To start with, we'll need to create a 2D dp array which has n plus one rows and w plus one columns.
Okay, so we have discussed this in detail in the previous video.
So let's go ahead and implement the code.
So I can say const dp is equal to array dot from.
And I have linked N plus one.
Okay.
Now over here we are going to say RA w plus one, and we will fill every cell in this 2d dp array with
the value zero.
Okay.
So we have created a 2d dp array which has n plus one rows and w plus one columns.
And we have filled every cell in this DP array with the value zero.
Okay, now let's proceed.
Now we have already seen that in the previous video that the first column and the first row need to
be filled with the value zero.
And that's taken care over here because we have in fact filled every cell in this DP array with the
value zero.
So now we are going to have a nested for loop.
And I is going to take the values starting at one because we don't need to now visit the row with index
zero.
So that's why I starts with one.
And I goes up to n okay.
And then we'll have j which also starts at one.
Because for the same reason we don't want to visit the first column or the column with index zero.
So that's why we start with j taking the value one and j goes up to w okay.
So j less than equal to w.
All right.
And now for each IJ combination we need to calculate the exclude value and the include value okay.
So okay that's a typo.
So let's say const exclude is equal to dp at I minus one j.
Okay.
So again we have discussed this.
Now the remaining weight does not change.
So that's why we have J itself over here.
And then we have to exclude this particular item.
So that's why we have I minus one over here.
That's exclude okay.
Now let's go ahead and calculate include.
Now initially we will set include to equal zero because we cannot always include the item.
And ultimately over here we would have to say DP at IJ is the maximum between exclude and include okay.
So that is why we need a value over here for the include variable.
And that's why initially we are setting it to zero.
And then we proceed and check whether the weight of this particular item is less than or equal to the
remaining weight, which is J.
Okay.
So if weight at I minus one less than equal to j.
And again over here we have to do I minus one.
And we have discussed the reason for this.
That is because the weight and value array are zero indexed.
Now again we have discussed this in detail in the previous video.
So I'm just proceeding with the solution over here.
So if weight at I minus one is less than or equal to j then we can include it.
So in that case include would be equal to value at I minus one plus d p at I minus one j minus weight
at I minus one okay.
So over here j minus weight at I minus one gives us the remaining weight after deducting the weight
of the item that has been added to the knapsack.
And then over here we have at I minus one because we have used the ith element.
So we have to go to the previous element.
And that's what we have done over here as well okay.
So this will give us the include value.
And then over here we are assigning depee at I j with the value which is the greater value between exclude
and include.
And.
In this way we will fill the DP table.
And then finally we can just return depee at n w.
And that will give us the answer.
Okay, now let's go ahead and run this code and see if it's passing all the test cases.
All right, so it's working.
It's passing all the test cases.
And again remember DPI at n w is the last element of the table.
And that would be representing the answer.
And we have discussed this in detail in the previous video.