> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/unbounded-knapsack-repetition-of-items-allowed.md).

# Unbounded Knapsack (Repetition of items allowed)

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 [classical Knapsack problem](https://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/), 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.
```

```java
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];
    }
}
```