The unbounded knapsack question is very similar to the zero one knapsack problem which we have previously
discussed.
The only difference is that any item can be taken any number of times, or in other words, repetition
with respect to taking the same item again and again is allowed.
Okay, so that's the only difference when we compare this question with the zero one knapsack problem.
We have already discussed the zero one knapsack problem in detail, where we first wrote the recursive
solution and then we memoized it.
And finally we discussed the tabulation approach as well as the space optimized tabulation approach.
So over here let's directly start with the tabulation approach because we are already familiar with
this question type.
So let's get started now to discuss how we can solve this question.
Let's take an example where let's say we are given three items.
So the values of the items are two, four and nine.
And their respective weights are eight, two and five.
And the capacity of the knapsack over here is given as eight units.
And again n is three, because we have three items in these two arrays.
Now to solve this we will need a 2d dp array which has w plus one columns and n plus one rows.
So this is the same approach that we have discussed in the zero one knapsack problem when we were discussing
the tabulation approach.
So we will have a similar DP table over here as well.
And notice that because w is eight we have nine columns.
And because n is equal to three we have four rows in this DP table.
Now before we go ahead and fill this DP table, let's quickly review what a particular cell means okay.
So for example what does this cell over here represent.
This cell over here will represent the maximum profit or the maximum value that we can get in a knapsack
where its capacity is four.
So this value gives the capacity of the knapsack.
And we can only take these two items okay.
Similarly this cell over here would represent the maximum value that we can have in the knapsack where
the weight limit of the knapsack is six.
And we can only take this particular item over here.
Now with this understanding let's try to fill the initial conditions in this DP table.
Now what would be the values in the first row over here.
Now from what we have over here, we can understand that the first row represents the scenario where
we have no item.
And if we have no item, then we cannot have any value in the knapsack.
And for that reason, we can fill all the cells in the first row with zero.
Similarly, when it comes to the first column, we can fill all these values with zero, because.
Notice for the first column, the weight limit of the knapsack is zero, and if the weight limit or
the capacity of the knapsack is zero, it means that we cannot add any item to the knapsack, and therefore
the value in the knapsack would be zero.
So these are the initial conditions for the DP table.
Now we would have to go through each of these cells and fill their respective values.
Now to do that for each cell we would have to calculate an include value and an exclude value.
And then the maximum between include and exclude will be the value that we will store in that particular
cell.
So this is the same thing that we did for the zero one knapsack problem as well.
So let's see how we can identify the value for dp at ij.
So I'm just writing the general solution over here.
Now to calculate exclude we just need to subtract I by one.
So exclude will equal dp at I minus one j.
Notice I j is still j itself because just by excluding there is no change in the weight, capacity or
the remaining weight that can be added to the knapsack, but we are just excluding an item.
So that's why I change this to I minus one.
Now what about the include value?
Now to calculate the include value, we will first have to check whether the item at hand can be included
or not.
Okay.
And for that we'll have to check whether weight at I minus one is less than or equal to the value at
J.
Okay.
Remember all these values represent j or for a particular cell you just need to see what's over here
to get the value for J.
And that represents the remaining capacity that can be added to the knapsack.
And we can add an item to the knapsack only if its weight is less than or equal to the remaining capacity
that can be added to the knapsack.
Now over here, when we are considering the item.
Term at index I in the deep table over here, or the item at the I th row.
Okay.
We have to do I minus one because the wait array is zero indexed.
For example notice over here item two is at the row with index two okay.
And item two in the values array or in the wait array is at index one.
Okay.
So we have to change this two over here to this one.
And that's why we have to do wait at I minus one.
Now let's assume that we found that wait at I minus one is indeed less than or equal to J.
And therefore we can go ahead and include that particular item to the knapsack.
Now when we include that particular item to the knapsack, the value of items in the knapsack will increase
by val at I minus one, and to that.
We'll have to add DP and I and then j minus weight at I minus one.
Now let's try to understand this.
So over here notice I have again I minus one over here as well as over here okay.
And that's for zero indexing as we have discussed okay.
So we have to change this two for example to one.
So that's why over here and over here we have to do I minus one.
So again the rule of thumb over here is that for changing the item at index I in the DP table is at
index I minus one in the value and weight array.
Okay.
So that explains why we have I minus one over here and over here.
And again we have seen why we have valid I minus one over here because we have added this item to the
knapsack.
And therefore the value of items in the knapsack would increase by this amount over here.
And because we have added this item, the remaining capacity or the remaining weight that can be added
to the knapsack has to decrease and for getting the remaining amount or the remaining capacity that
can be added to the knapsack, we have to do j minus weight at I minus one.
And over here notice we still have DP at I, even though we included an item to the knapsack.
And that's because in the question, it's mentioned that an item can be added to the knapsack an unlimited
number of times.
So this is where this question over here differs from the zero one knapsack question.
And again the difference was there.
You could add an item only once.
But over here you can add an item an unlimited number of times okay.
So we have seen that include is valid I minus one plus DP at I.
And then you have j minus weight at I minus one.
And we have seen that this over here gives the remaining capacity that can be added to the knapsack.
So at this point we have calculated exclude and include and then we would have to find the maximum between
these two.
And that value would be filled at dp at I j.
Now we're going to do this for all of these remaining cells.
And once we have filled all of these up we will get the answer at this particular cell over here which
is DP at n w.
And again why is that.
So it is the case because this cell over here represents the maximum profit that can be added to the
knapsack where the capacity of the knapsack is eight.
And we can consider all these three items.
And notice that that in fact is what the question asks us to find.
So that's why we will get the answer over here.
And we'll just have to return that.
So this is the approach that we will take to solve this question.
In the next video, let's try to think of the space and time complexity of the approach that we came
up with over here.