Problem Statement
We are going to deal with the well known knapsack problem with an additional constraint in this blog. We are given a list of N items and a knapsack of size W. Every item has a cost ci and value vi associated with it (1 ≤ i ≤ N). We can select some items from the list such sum of the cost of all the selected items does not exceed W. The addition constraint is that . This is also known as the 0/1 knapsack problem.
The bounded knapsack problem
The bounded knapsack problem is like the 0/1 knapsack problem, except in this we are also given a count for each item. In other words, each item has a count si associated with it and we can select an item si times (1 ≤ i ≤ N).
Solving bounded knapsack problem
The solution is simple. Let dp[i][j] denote the maximum sum of value we can get while using first i items with a total cost of j