## Problem Statement

Given a knapsack weight W and a set of N items with certain values(benefit or profit) val, and weights wt, find the maximum amount that could make up the exact knapsack weight.

In **Unbounded Knapsack**, you may select an item multiple times.

## Example

N = 4

W = 10

val[] = {15, 25, 20, 10}

wt[] = {3, 4, 6, 8}

## Example Explanation

Therefore to get the best outcome the selected items are :

Item number `2`

, with weight `4`

yields a profit of `25`

.

Item number `1`

, with weight `3`

yields a profit of `15`

.

Item number `1`

, with weight `3`

yields a profit of `15`

.

Therefore total profit using the unbounded knapsack will be $25+15+15 = 55$.

## Input/Output

**Input**

- The
**first line of input**integer N represents the number of items. - The
**second line**contains an array val of length N that contains values of the items. - The
**third line**contains an array wt of length N that contains the weights of the items. - The
**fourth line**contains the integer W which represents the total weight of the knapsack.

**Output**

The first and only line of the output contains an integer that represents the maximum profit that can be obtained without crossing the weight limit of the knapsack.

## Constraints

$1 ~≤ ~N~,~ W ~≤ ~1000$

$1 ~≤ ~val[i]~, ~wt[i] ~≤ ~100$

## Algorithm 1 – Brute Force Approach – Recursive Approach

### Algorithm

**Step 1 –**Begin by calling the recursive function`‘unboundedKnapsack()’`

that takes parameters W, index, val, and wt.**Step 2 –**Set the base case that if`‘index’ = 0`

or`‘W’ = 0`

function returns 0.**Step 3 –**Next, check if the weight of the item at the index is more than the knapsack weight ‘W’.- If yes then return the result obtained after recursively calling the
`‘unboundedKnapsack()’`

function for the remaining elements. - Else using the max function return the maximum of the following
- result obtained by calling the recursive function
`‘getMaxVal()’`

for ‘index – 1’ and ‘W – weight[index]’. - result obtained by calling the recursive function ‘
`unboundedKnapsack()`

’ for ‘`index - 1`

’ items with ‘W’ weight.

- result obtained by calling the recursive function

- If yes then return the result obtained after recursively calling the

### Code Implementation

**C++**

```
/* Java program to find maximum profit with an unbounded knapsack of weight W.*/
#include<iostream>
#include<algorithm>
using namespace std;
/* Recursive function of unbounded Knapsack problem to return maximum value with knapsack capacity (without using any extra space)*/
static int unboundedKnapsack(int W, int index, int val[], int wt[]){
/* Base case of recursion with only one item.*/
if (index == 0) {
return (W / wt[0]) * val[0];
}
/* If the wt of an item at index is more than W it cannot be included. */
if (wt[index] > W){
return unboundedKnapsack(W, index - 1, val, wt);
}
/* Case 1: Solution does not include the item at the index */
int item_not_included = 0 + unboundedKnapsack(W,index-1,val,wt);
/* Case 2: Item at index is included in solution */
int item_included = val[index] + unboundedKnapsack(W-wt[index],index,val,wt);
/*return maximum of the above cases*/
return max(item_included,item_not_included);
}
// Driver code
int main(){
int N, i, W;
cout<<"Enter the number of items: ";
cin>>N;
int val[N], wt[N];
cout<<"Enter value of the items: ";
for(i=0; i<N; i++){
cin>>val[i];}
cout<<"Enter weight of the items: ";
for(i=0; i<N; i++){
cin>>wt[i];}
cout<<"Enter the weight of the knapsack: ";
cin>>W;
cout<<"The maximum profit that can be obtained is : ";
cout<<unboundedKnapsack(W, N-1, val, wt);
}
```

**Java**

```
/* Java program to find maximum profit with an unbounded knapsack of weight W.*/
import java.io.*;
import java.util.*;
class Main {
/* Function to return a maximum of two integers */
static int max(int a, int b){
if(a>b)
{return a;}
else
{return b;}
}
/* Recursive function of unbounded Knapsack problem to return maximum value with knapsack capacity (without using any extra space)*/
static int unboundedKnapsack(int W, int index, int val[], int wt[]){
/* Base case of recursion with only one item.*/
if (index == 0) {
return (W / wt[0]) * val[0];
}
/* If the wt of an item at index is more than W it cannot be included. */
if (wt[index] > W){
return unboundedKnapsack(W, index - 1, val, wt);
}
/* Case 1: Solution does not include the item at the index */
int item_not_included = 0 + unboundedKnapsack(W,index-1,val,wt);
/* Case 2: Item at index is included in solution */
int item_included = val[index] + unboundedKnapsack(W-wt[index],index,val,wt);
/*return maximum of the above cases*/
return max(item_included,item_not_included);
}
// Driver code
public static void main(String args[]){
int N, i, W;
Scanner sc=new Scanner(System.in);
System.out.print("Enter the number of items: ");
N=sc.nextInt();
int[] val = new int[N];
System.out.print("Enter value of the items: ");
for(i=0; i<N; i++){
val[i]=sc.nextInt();}
int[] wt = new int[N];
System.out.print("Enter weight of the items: ");
for(i=0; i<N; i++){
wt[i]=sc.nextInt();}
System.out.print("Enter the weight of the knapsack: ");
W=sc.nextInt();
System.out.print("The maximum profit that can be obtained is : ");
System.out.println(unboundedKnapsack(W, N-1, val, wt));
}
}
```

**Python**

```
# Python program to find maximum profit with an unbounded knapsack of weight W.
# Recursive function of unbounded Knapsack problem to return maximum value with a knapsack capacity (without using any extra space)
def unboundedKnapsack(W, index, val, wt):
#Base case of recursion with only one item.
if index==0 :
return (W//wt[0])*val[0]
# If the wt of an item at index is more than W it cannot be included.
if (wt[index] > W):
return unboundedKnapsack(W, index - 1, val, wt)
# Case 1: Solution does not include the item at the index
item_not_included=0+unboundedKnapsack(W,index-1,val,wt)
# Case 2: Item at the index is included in the solution
item_included=val[index]+unboundedKnapsack(W-wt[index],index,val,wt)
# return a maximum of the above cases
return max(item_included,item_not_included)
# Driver program
if __name__ == '__main__':
N = int(input("Enter the number of items: "))
val = list(map (int, input ("Enter value of the items: ").split ()))
wt = list(map (int, input ("Enter weight of the items: ").split ()))
W = int(input("Enter the weight of the knapsack: "))
print("The maximum profit that can be obtained is :", end=" ")
print(unboundedKnapsack(W, N-1, val, wt))
```

### Output

```
Enter the number of items: 4
Enter value of the items: 15 25 20 10
Enter weight of the items: 3 4 6 8
Enter the weight of the knapsack: 90
The maximum profit that can be obtained is : 55
```

### Time Complexity

The recursive calls increase at a rate of `2`

until ‘N’ or ‘W’ becomes `0`

, as every function calls itself twice.

Thus the maximum possible calls are $2^N$. The overall time complexity for this approach will be $O(2^N)$.

### Space Complexity

The recursive approach is based on calculating the total weight and value of all subsets without using any additional data structure. Since no extra space is required the space complexity for this approach will be **O(1)**.

## Algorithm 2 – Bottom-Up Approach – Dynamic Programming – Iteration + Tabulation

### Algorithm

**Step 1 –**Initialize a 2D array ‘dp’ of size $(N + 1) * (W)$ and fill it with`-1`

.**Step 2 –**Call the recursive function ‘`unboundedKnapsack()`

’ that takes parameters W, N, val, and wt.**Step 3 –**To find the maximum profit for every sub-array and every possible Knapsack Weight use dp as a table where:- Either exclude the item and consider profit obtained from the sub-array excluding it
`dp[i - 1][j]`

. - Or include the item if weight is lesser than the knapsack weight available
`val[i] + dp[i][j - wt[i]]`

and consider the maximum of the two.

- Either exclude the item and consider profit obtained from the sub-array excluding it

### Code Implementation

**C++**

```
/* CPP program to find maximum profit with an unbounded knapsack of weight W.*/
#include <bits/stdc++.h>
using namespace std;
/* function of unbounded Knapsack problem to return maximum value with knapsack capacity*/
int unboundedKnapsack(int W, int N, int val[], int wt[]){
vector<vector<int> > dp(N, vector<int>(W + 1, -1));
int i=0,j=0;
/* Get the values for the considered item for every capacity */
for(i=1; i<=W; i++)
dp[0][i] = ((i / wt[0]) * val[0]);
/* For each item, check for every possible weight*/
for(i=1; i<N; i++){
for(j=1; j<W+1; j++){
if (wt[i] <= j)
dp[i][j] = max(dp[i - 1][j], val[i] + dp[i][j - wt[i]]);
else
dp[i][j] = dp[i - 1][j];
}
}
return dp[N-1][W];
}
// Driver code
int main(){
int N, i, W;
cout<<"Enter the number of items: ";
cin>>N;
int val[N], wt[N];
cout<<"Enter value of the items: ";
for(i=0; i<N; i++){
cin>>val[i];}
cout<<"Enter weight of the items: ";
for(i=0; i<N; i++){
cin>>wt[i];}
cout<<"Enter the weight of the knapsack: ";
cin>>W;
cout<<"The maximum profit that can be obtained is : ";
cout<<unboundedKnapsack(W, N-1, val, wt);
return 0;
}
```

**Java**

```
/* Java program to find maximum profit with an unbounded knapsack of weight W.*/
import java.io.*;
import java.util.*;
class Main {
/*Function that returns a maximum of two integers */
static int max(int a, int b) {
if(a>b)
{return a;}
else
{return b;}
}
/* function of unbounded Knapsack problem to return maximum value with knapsack capacity*/
static int unboundedKnapsack(int W, int N, int val[], int wt[]){
int[][] dp = new int[N][W + 1];
for (int row[] : dp)
Arrays.fill(row, -1);
int i=0,j=0;
/* Get the values for the considered item for every weight */
for(i=1; i<=W; i++){
dp[0][i] = ((i / wt[0]) * val[0]);
}
/* For each item, check for every possible weight */
for(i=1; i<N; i++){
for(j=1; j<W+1; j++){
if (wt[i] <= j){
dp[i][j] = max(dp[i - 1][j], val[i] + dp[i][j - wt[i]]);
}
else{
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[N-1][W];
}
// Driver code
public static void main(String args[]){
int N, i, W;
Scanner sc=new Scanner(System.in);
System.out.print("Enter the number of items: ");
N=sc.nextInt();
int[] val = new int[N];
System.out.print("Enter value of the items: ");
for(i=0; i<N; i++){
val[i]=sc.nextInt();}
int[] wt = new int[N];
System.out.print("Enter weight of the items: ");
for(i=0; i<N; i++){
wt[i]=sc.nextInt();}
System.out.print("Enter the weight of the knapsack: ");
W=sc.nextInt();
System.out.print("The maximum profit that can be obtained is : ");
System.out.println(unboundedKnapsack(W, N, val, wt));
}
}
```

**Python**

```
"""Python program to find maximum profit with an unbounded knapsack of weight W."""
# function of unbounded Knapsack problem to return maximum value with a knapsack capacity
def unboundedKnapsack(W, N, val, wt):
row = [0] * (W + 1)
dp = [row] * N
# Get the values for the considered item for every capacity
for i in range(W + 1):
dp[0][i] = (i // wt[0]) * val[0]
# For each item, check for every possible weight or capacity
for i in range(1, N):
for j in range(1, W + 1):
if (wt[i] <= j):
dp[i][j] = max(dp[i - 1][j], val[i] + dp[i][j - wt[i]])
else:
dp[i][j] = dp[i - 1][j]
return dp[i][j]
# Driver program
if __name__ == '__main__':
N = int(input("Enter the number of items: "))
val = list(map (int, input ("Enter value of the items: ").split ()))
wt = list(map (int, input ("Enter weight of the items: ").split ()))
W = int(input("Enter the weight of the knapsack: "))
print("The maximum profit that can be obtained is :", end=" ")
print(int(unboundedKnapsack(W, N, val, wt)))
```

### Output

```
Enter the number of items: 4
Enter value of the items: 15 25 20 10
Enter weight of the items: 3 4 6 8
Enter the weight of the knapsack: 10
The maximum profit that can be obtained is : 55
```

### Time Complexity

Since `N * W`

subproblems are considered the overall time complexity for this approach will be **O(N * W)**.

### Space Complexity

As a new 2D array ‘dp’ is being introduced,

Therefore, the overall space complexity for this approach will be **O(N * W)**.

## Algorithm 3 – Top-down Approach – Dynamic Programming with Memoization

### Algorithm

The top-down approach aims at removing duplicate calls by using an array to store the state of ‘N’ and ‘W’.

**Step 1-**Initialize a 2D array ‘dp’ of size $(N + 1) * (W)$ and fill it with`-1`

.**Step 2 –**Call the recursive function ‘`unboundedKnapsack()`

’ that takes parameters W, index, val, wt, and dp.**Step 3 –**Set the base case that if`‘index’ = 0`

or`‘W’ = 0`

function returns`0`

.**Step 4-**Next, check if the value is present in the array. If yes, then return the value.**Step 5 –**Next, check if the weight of the item at the index is more than the knapsack weight ‘W’.- If yes then return the result obtained after recursively calling the ‘
`unboundedKnapsack()`

’ function for the remaining elements. - Else return the maximum of the following
- result obtained by calling the recursive function ‘
`getMaxVal()`

’ for ‘`index - 1`

’ and ‘`W - weight[index]`

’. - result obtained by calling the recursive function ‘
`unboundedKnapsack()`

’ for ‘`index - 1`

’ items with ‘W’ weight.

- result obtained by calling the recursive function ‘

- If yes then return the result obtained after recursively calling the ‘

### Code Implementation

**C++**

```
/* CPP program to find maximum profit with an unbounded knapsack of weight W.*/
#include <bits/stdc++.h>
using namespace std;
/* function of unbounded Knapsack problem to return maximum value with knapsack capacity*/
int unboundedKnapsack(int W, int index, int val[], int wt[], vector<vector<int> >& dp){
/* Base case of recursion with only one item.*/
if (index == 0)
return (W / wt[0]) * val[0];
/* Return if the value is pre-calculated */
if (dp[index][W] != -1)
return dp[index][W];
/* If the wt of an item at index is more than W it cannot be included. */
if (wt[index] > W)
return unboundedKnapsack(W, index - 1, val, wt, dp);
/* Case 1: Solution does not include the item at the index */
int item_not_included = unboundedKnapsack(W, index-1, val, wt, dp);
/* Case 2: Item at index is included in solution */
int item_included = val[index] + unboundedKnapsack(W-wt[index], index, val, wt, dp);
/*return maximum of the above cases*/
return dp[index][W] = max(item_included, item_not_included);
}
// Driver code
int main(){
int N, i, W;
cout<<"Enter the number of items: ";
cin>>N;
int val[N], wt[N];
cout<<"Enter value of the items: ";
for(i=0; i<N; i++){
cin>>val[i];}
cout<<"Enter weight of the items: ";
for(i=0; i<N; i++){
cin>>wt[i];}
cout<<"Enter the weight of the knapsack: ";
cin>>W;
cout<<"The maximum profit that can be obtained is : ";
/* Introducing 2D array dp. */
vector<vector<int> > dp(N, vector<int>(W + 1, -1));
cout<<unboundedKnapsack(W, N-1, val, wt, dp);
return 0;
}
```

**Java**

```
/* Java program to find maximum profit with an unbounded knapsack of weight W.*/
import java.io.*;
import java.util.*;
class Main {
/*Function that returns a maximum of two integers */
static int max(int a, int b) {
if(a>b)
{return a;}
else
{return b;}
}
/* function of unbounded Knapsack problem to return maximum value with knapsack capacity*/
static int unboundedKnapsack(int W, int index, int val[], int wt[], int dp[][]){
/* Base case of recursion with only one item.*/
if (index == 0){
return (W / wt[0]) * val[0];}
/* Return if the value is pre-calculated */
if (dp[index][W] != -1){
return dp[index][W];}
/* If the wt of an item at index is more than W it cannot be included. */
if (wt[index] > W){
return unboundedKnapsack(W, index - 1, val, wt, dp);}
/* Case 1: Solution does not include the item at the index */
int item_not_included = unboundedKnapsack(W, index-1, val, wt, dp);
/* Case 2: Item at index is included in solution */
int item_included = val[index] + unboundedKnapsack(W-wt[index], index, val, wt, dp);
/*return maximum of the above cases*/
return dp[index][W] = max(item_included, item_not_included);
}
// Driver code
public static void main(String args[]){
int N, i, W;
Scanner sc=new Scanner(System.in);
System.out.print("Enter the number of items: ");
N=sc.nextInt();
int[] val = new int[N];
System.out.print("Enter value of the items: ");
for(i=0; i<N; i++){
val[i]=sc.nextInt();}
int[] wt = new int[N];
System.out.print("Enter weight of the items: ");
for(i=0; i<N; i++){
wt[i]=sc.nextInt();}
System.out.print("Enter the weight of the knapsack: ");
W=sc.nextInt();
System.out.print("The maximum profit that can be obtained is : ");
/* Introducing 2D array dp.*/
int[][] dp = new int[N][W + 1];
for (int row[] : dp)
Arrays.fill(row, -1);
System.out.println(unboundedKnapsack(W, N-1, val, wt, dp));
}
}
```

**Python**

```
"""Python program to find maximum profit with an unbounded knapsack of weight W."""
#function of unbounded Knapsack problem to return maximum value with a knapsack capacity
def unboundedKnapsack( W, index, val, wt, dp):
# Base case of recursion with only one item.
if (index == 0):
return (W // wt[0]) * val[0];
#Return if the value is pre-calculated
if (dp[index][W] != -1):
return dp[index][W];
# If the wt of an item at index is more than W it cannot be included.
if (wt[index] > W):
return unboundedKnapsack(W, index - 1, val, wt, dp)
# Case 1: Solution does not include the item at the index
item_not_included = unboundedKnapsack(W, index-1, val, wt, dp)
# Case 2: Item at the index is included in the solution
item_included = val[index] + unboundedKnapsack(W-wt[index], index, val, wt, dp)
#return a maximum of the above cases
dp[index][W] = max(item_included, item_not_included)
return dp[index][W]
# Driver program
if __name__ == '__main__':
N = int(input("Enter the number of items: "))
val = list(map (int, input ("Enter value of the items: ").split ()))
wt = list(map (int, input ("Enter weight of the items: ").split ()))
W = int(input("Enter the weight of the knapsack: "))
print("The maximum profit that can be obtained is :", end=" ")
# Introducing 2D array dp.
row = [-1]*(W + 1)
dp = [row]*N
print(int(unboundedKnapsack(W, N-1, val, wt, dp)))
```

### Output

```
Enter the number of items: 4
Enter the value of the items: 15 25 20 10
Enter the weight of the items: 3 4 6 8
Enter the weight of the knapsack: 10
The maximum profit that can be obtained is : 55
```

### Time Complexity

Since `N * W`

recursive calls are made the overall time complexity for this approach will be **O(N * W)**.

### Space Complexity

As a new 2D array ‘dp’ is being introduced, the space complexity will be `O(N * W)`

.

Again, `O(N)`

space is required for the recursive call stack.

Therefore, the overall space complexity for this approach will be **O(N * W) + O(N)**.

## FAQ

**Q.** What is a Knapsack Problem?

**A.** A knapsack problem deals with a set of items that have some assigned weight and value. The main goal of the problem is to fill the knapsack with the maximum possible value within the given weight constraint.

**Q** What are the different knapsack problems?

**A.** There are 3 types of knapsack problems.

a) Fractional Knapsack

b) 0/1 Knapsack

c) Unbounded Knapsack

**Q.** What is the difference between a 0/1 knapsack and an unbounded knapsack?

**A.** The difference between 0/1 Knapsack and Unbounded Knapsack is that the latter allows the utilization of an infinite number of items.

**Q.** Name some problems related to unbounded knapsack?

**A.** Rod cutting, coin change, and maximum ribbon cut problems are related to the unbounded knapsack problem.

## Conclusion

- The unbounded knapsack problem has no upper bound on the number of copies of each kind of item.
**Approach 1 –**Trying all possible combinations of items and computing the maximum of those profits.- Time Complexity: $O(2^N)$
- Space Complexity: $O(1)$

**Approach 2 –**Using a 2D array, such that the last cell of dp stores the maximum value which can be achieved using all items and i capacity of the knapsack.- Time Complexity: $O(N * W)$
- Space Complexity: $O(N * W)$

**Approach 3 –**Using memory to return similar encounters from the array, instead of recomputing it.- Time Complexity: $O(N * W)$
- Space Complexity: $O(N * W) + O(N)$