Coding Pattern : Unbounded Knapsack Dynamic Programming
This is a continuation to my earlier post about 0/1 Knapsack dynamic programming article, if you have not read that I would strongly urge you to go through it first as this article builds on that. Click the below link to navigate there.
Coming back to unbounded knapsack dynamic programming, the only difference between 0/1 knapsack (aka bounded knapsack) and unbounded knapsack is that there is no limitation of choosing multiple instances of the same category of items.
Taking the same example which, I had used in 0/1 Knapsack article.
Let's say we have a Knapsack of capacity 7. We have items with weights and values as below. We are required to find the max value of the combined knapsack such that the total weight is less than equal to the capacity 7.
weights = [1, 2, 7]
values = [10, 5, 8]
In case of 0/1 knapsack, we could only choose one instance of each type, which means I can only choose 1 instance of value [10,5,8]. So naturally in that case the maximum came…
