Given a knapsack weight W and a set of n items with certain value vali and weight wti, we need to calculate the maximum amount that could make up this quantity exactly. This is different from classical 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.

2-D Approach: Space Complexity = O(n^2)

// Returns the maximum value that
// can be put in a knapsack of capacity W
int UnboundedKnapSack(int W, int wt[], int val[], int n)
{
    int i, w;
    int K[n + 1][W + 1];
 
    // Build table K[][] in bottom up manner
    for(i = 0; i <= n; i++)
    {
        for(w = 0; w <= W; w++)
        {
            if (i == 0 || w == 0)
                K[i][w] = 0;
            else if (wt[i - 1] <= w)
                K[i][w] = max(val[i - 1] +
                                K[i][w - wt[i - 1]],
                                K[i - 1][w]);
            else
                K[i][w] = K[i - 1][w];
        }
    }
    return K[n][W];
}

1-D Approach: Space Complexity = O(n)

Its an unbounded knapsack problem as we can use 1 or more instances of any resource. A simple 1D array, say dp[W+1] can be used such that dp[i] stores the maximum value which can achieved using all items and i capacity of knapsack. Note that we use 1D array here which is different from classical knapsack where we used 2D array. Here number of items never changes. We always have all items available.We can recursively compute dp[] using below formula

dp[i] = 0
dp[i] = max(dp[i], dp[i-wt[j]] + val[j]
                   where j varies from 0
                   to n-1 such that:
                   wt[j] <= i

result = d[W]

// C++ program to find maximum achievable value
// with a knapsack of weight W and multiple
// instances allowed.
#include<bits/stdc++.h>
using namespace std;
 
// Returns the maximum value with knapsack of
// W capacity
int unboundedKnapsack(int W, int n,
                       int val[], int wt[])
{
    // dp[i] is going to store maximum value
    // with knapsack capacity i.
    int dp[W+1];
    memset(dp, 0, sizeof dp);
 
    // Fill dp[] using above recursive formula
    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];
}

Another Approach

// Time Complexity : O(n^2)
// Space Complexity : O(n)
// Just swap the places of bolded 0 and 1 and it will convert into bounded KS
class Solution{
public:
    int knapSack(int N, int W, int val[], int wt[])
    {
        vector<vector<int>> dp(2,vector<int>(W+1,0));
        
        for(int i=0;i<N;i++)
        {
            int j = 1;
            
            if(i%2==0) //currently we have odd number of elements
            {
               while(j<=W)
               {
                   if(j>=wt[i])
                   dp[0][j] = max(dp[**0**][j-wt[i]]+val[i],dp[1][j]);
                   
                   else
                   dp[0][j] = dp[1][j];
                   
                   j++;
               }
            }
            else //currently we have even number of elements
            {
                 while(j<=W)
                 {
                   if(j>=wt[i])
                   dp[1][j] = max(dp[**1**][j-wt[i]]+val[i],dp[0][j]);
                   
                   else
                   dp[1][j] = dp[0][j];
                   
                   j++;
                 }
            }
            
        }
        
        return N%2 ? dp[0][W] : dp[1][W];
    }
};