Given a knapsack weight W and a set of n items with certain value vali and weight wti, we need to calculate minimum amount that could make up this quantity exactly. This is different from , here we are allowed to use unlimited number of instances of an item.
Examples:
Input : W = 100
val[] = {1, 30}
wt[] = {1, 50}
Output : 100
There are many ways to fill knapsack.
1) 2 instances of 50 unit weight item.
2) 100 instances of 1 unit weight item.
3) 1 instance of 50 unit weight item and 50
instances of 1 unit weight items.
We get maximum value with option 2.
Input : W = 8
val[] = {10, 40, 50, 70}
wt[] = {1, 3, 4, 5}
Output : 110
We get maximum value with one unit of
weight 5 and one unit of weight 3.
class Solution {
public int unboundedKnapsack(int W, int n, int[] val, int[] wt) {
// dp[i] is going to store maximum value
// with knapsack capacity i.
int dp[] = new int[W + 1];
for (int i = 0; i <= W; i++)
for (int j = 0; j < n; j++)
if (wt[j] <= i)
dp[i] = max(dp[i], dp[i - wt[j]] + val[j]);
return dp[W];
}
}