Let's now get into the code for solving the unbounded knapsack problem.
And we are going to directly get into the tabulation approach.
Okay.
Now again over here.
This is just going to be a tiny difference between the approach that we have taken to solve the zero
one knapsack problem.
So initially let's create a DP array okay.
Which will have n plus one rows and w plus one columns.
So let's go ahead and do that.
Linked is n plus one, and the number of columns that we need is W plus one.
And we are going to fill every cell in this 2d dp array with the value zero initially.
Okay.
And now we are going to iterate through the cells in the DP array.
And we are going to leave out the first row and first column because we just need the values zero over
there.
And we already have taken care of that over here.
Okay.
And this is pretty similar to what we did in the zero one knapsack problem.
So again let's have a nested for loop over here for let I equal to one I less than equal to n okay.
And j is going to take the values from one up to w.
Okay, now for each combination of I and J, we have to calculate the exclude value and the include
value.
So exclude is going to equal depee at I minus one j because we are excluding the item and in the ith
row over here.
And when it comes to include initially we will set it to zero.
And we have discussed why this is required when we discussed the zero one knapsack problem.
And ultimately we are going to say depee at I j is the maximum between exclude and include.
Okay, so there's no change over here.
Now the only change is going to be the fact that over here we can include an item multiple times.
So over here again let's have the criteria.
Let's have the check over here to determine whether this particular item can be included or not.
So if weight at I minus one is less than or equal to j, then this item can be included and include
would be equal to value at I minus one plus d p at I and j minus weight at I minus one.
Now over here we see the difference when we solve these zero one knapsack problem.
Over here we had DP at I minus one because an item could be included only one time, but because in
this case an item can be included multiple times.
Even though we included the item in the ith row, we don't need to shift to the I minus one row, but
rather we stay over here itself.
That is, we have DP at I itself over here and that's it.
So this should help us solve this question.
Now at the end we need to return the p n w.
So let's go ahead and do that over here.
And that's it.
Now let's go ahead and run this code and see if it's passing all the test cases.
Okay.
So there's an error.
I think I've made a typo so it should be excluded.
I think I've missed the C so yeah it's exclude here right.
So let's correct that and let's again run this code.
All right.
So there's one more error.
So over here instead of J I've written I okay.
Sorry for that.
Now let's again run this code and see if it's working.
And you can see that it's passing all the test cases.