The unbounded knapsack determines the most valuable collection of objects that can fit in a knapsack of a particular volume given several sorts of items of various values and volumes.
The unbounded knapsack problem is based on dynamic programming and is an extension of the basic 0-1 knapsack problem. You may learn more about the 0-1 knapsack problem here. The only difference between 0/1 Knapsack and Unbounded Knapsack is that we may utilize an infinite number of items in this case.
Among the several types of knapsack problems, this article will discuss the unbounded knapsack problem in detail.
Since it is essential first to understand how an unbounded knapsack is different from the rest.
There is a brief explanation of the various kinds of knapsack problems and the primary difference in the algorithm for unbounded knapsacks from the rest of them.
In this blog, we have also used an example and its code snippet to understand the concept better.
Knapsack problems are combinatorial optimization problems used to illustrate both problem and solution.
A knapsack problem includes a given set of items having some assigned weight and value, and the goal is to add the most value to the knapsack within the given weight constraint.
In such problems, there are items and a bag (knapsack) where:
Input is the weight array and the value array (‘N’ set of items)
Output must be the maximum possible profit
TheConstraint is the weight (usually denoted by ‘W’ or ‘C’)
This is a ‘greedy’ type that allows items to be divided if the bag’s capacity doesn’t allow the entire item.
For example, if ‘W’ is 10 kg and the bag is filled up to 9 kg, a 2 kg item cannot be added to it. In this case, a fractional knapsack would allow just a fraction of the item to be added (1 kg here) and divide its value accordingly (dividing to half in this case).
0-1 Knapsack
The 0-1 knapsack is named so because it either takes an item as a whole or not at all. If the bag’s capacity is 10 kg and filled up to 9 kg, it cannot pick a 2 kg item to be added. Moreover, among all the items given, one item can only be picked once for the knapsack.
Unbounded Knapsack
The unbounded knapsack too can only take items as a whole and not in parts or fractions.
However, an item first picked for the knapsack can be chosen again in the next iteration.
The only difference between the code for 0-1 and unbounded knapsack would be that the already picked elements won’t be considered the second time in the case of 0-1 knapsack, but for unbounded knapsack, the entire array will be considered all over again.
Recommended: Try the Problem yourself before moving on to the solution
Recursive Approach for Unbounded Knapsack
Algorithm
First, the maximum value in the unbounded knapsack is returned by the function ‘max()’ using the ternary operation.
In the ‘knapSack()’ function, the maximum capacity, weight of items in an array, and value of items in an array are taken as parameters.
The base case in the function would be if the total capacity is 0 or the weight of the current item will be 0 then return 0 to the function.
If the weight of the item is more than the total capacity, then the item cannot be included in the knapsack and the Recursive call will be made for the rest of the elements.
The else statement will call the max function to help return the maximum of 2 cases: either the nth item will be included or the nth item will not be included in the solution. But if the element is not included then we can reconsider that element once again for the other solution.
The driver code will finally call the function and calculate the maximum output.
Code Snippet
class unboundedKnapsack
{
// Function to return the maximum of two integers
static int max(int i, int j)
{
return (i > j) ? i : j;
}
// Returns the maximum value for capacity C
static int knapSack(int C, int weight[], int value[], int n)
{
/*
Weight of nth item can’t be more than C
item cannot be included.
*/
if (n == 0 || C == 0)
return 0;
if (weight[n - 1] > C)
return knapSack(C, weight, value, n - 1);
// return maximum of the following cases:
// 1. nth item will be included
// 2. nth item not included
else
return max(value[n - 1]+ knapSack(C - weight[n - 1], weight,
value, n), knapSack(C, weight, value, n - 1));
}
// Driver code
public static void main(String args[])
{
int value[] = new int[] { 25, 30, 15 };
int weight[] = new int[] { 15, 5, 10 };
int C = 100;
int n = value.length;
System.out.println(knapSack(C, weight, value, n));
}
}
You can also try this code with Online Java Compiler
In every recursive call, 2 more calls are made to the same function. This means that the calls increase at a rate of 2 until ‘N’ or ‘C’ reaches 0.
The maximum possible calls in this program would be ‘2 ^ N’. Hence, the overall time complexity will be O(2 ^ N).
Space Complexity: O(1)
Since we are using constant space, the overall space complexity will be O(1).
Another approach for unbounded knapsack is thedynamic programming top-down approach.
The previous approach for unbounded knapsack has numerous duplicate calls for the same state ‘N’ and ‘C’, leading to exponential complexity.
Such an algorithm will run forever if the value of ‘N’ and ‘C’ is high.
This can be avoided by using an array and storing the state of ‘N’ and ‘C’ in that array.
Whenever the same state is encountered during execution, the program will return it from the array, rather than recomputing it.
Such an approach will decrease the time complexity significantly.
Algorithm
In a function, initialize a 2D array of size (N + 1) * (C + 1) and call the recursive function ‘getMaxVal()’ that takes the following values: ‘C’ - the weight of knapsack; ‘value’ - an array containing the value of items, ‘weight’ - an array to store the weight of the item, and ‘N’ - number of items
Base case will be if ‘N’ = 0 or ‘C’ = 0 then return 0.
Next, check if the value is present in the array. If yes, then return the value.
After that, check if the weight of the ‘Nth’ item is more than the current weight ‘C’ then recursively call the same function ‘getMaxVal()’ for ‘N - 1’ items and ‘C’ weight, assign it to array[N][C] return the result.
Else get the maximum of the last two steps and assign the result to array[N][C] and return it.
Call the recursive function ‘getMaxVal()’ for ‘N - 1’ and ‘C’ - weight[N].
Finally, call the recursive function ‘getMaxVal()’ for ‘N - 1’ items with ‘C’ weight.
Code Snippet
public class Solution{
int getMaxVal(int C, int weight[], int value[], int n, int[][] arr) {
// Base Case
if (n == 0||C == 0){
return 0;
}
if (arr[n][C] != -1){
return arr[n][C];
}
// If weight is more than current knapsack weight then we have to exclude this item
if (C < weight[n - 1]){
int maxValue = getMaxVal(C, weight, value, n - 1,arr);
arr[n][C] = maxValue;
return maxValue;
}
else{
// Pick Nth item and add its value in result
int valueWithNthItem = getMaxVal(C - weight[n - 1], weight, value, n - 1, arr) + value[n - 1];
// Exclude Nth item and go for n-1 items
int valueWithoutNthItem = getMaxVal(C, weight, value, n - 1, arr);
// Get the maximum of both values
int maxValue = Math.max(valueWithNthItem, valueWithoutNthItem);
arr[n][C] = maxValue;
return maxValue;
}
}
int getMaximumKnapsack(int C, int weight[], int value[], int n){
// Initialize 2D array of size N + 1 and w + 1 with value -1
int arr[][] = new int[n + 1][C + 1];
for(int i = 0; i < n + 1; i++){
for(int j = 0; j < C + 1; j++){
arr[i][j] = -1;
}
}
return getMaxVal(C, weight, value, n, arr);
}
public static void main(String[] args)
{
Solution solution = new Solution();
int val[] = new int[] { 25, 30, 15 };
int wt[] = new int[] { 15, 5, 10 };
int C = 60;
int n = val.length;
int maxValue = solution.getMaximumKnapsack(, wt, val, n);
System.out.println("Maximum value that the knapsack can have is : " + maxValue);
}
}
You can also try this code with Online Java Compiler
There will be ‘N * C’ calls in a recursive functionas we are using a 2D array, and if the value is present in this array, then we are not making duplicate calls.
So there will be utmost N * C combinations. Therefore the overall time complexity is O(N * C).
Space Complexity: O(N * C)
As we are using a 2D array of size ‘N * C’. Therefore the overall space complexity is O(N * C).
First, the maximum of two numbers is returned to find out the maximum value that can be used in a knapsack with the capacity ‘C’.
Then, a 2D array with ‘n + 1’ rows and ‘C +1’ columns is created. (‘N’ being the number of items.
The bottom-up approach is used to fill table/2-D array ‘K’.
The for loop will run as long as the weight of the item is less than or equal to the total capacity.
In a for loop, the base case would be if the weight of the nth item is more than the total capacity, or if the total capacity is 0.
Otherwise, the knapsack function is called again
The else statement will call the max function to help return the maximum of 2 cases again.
The driver code will finally call the function and calculate the maximum output.
Code Snippet
// Solution using 2D array in dynamic approach
class unboundedKnapsack{
// function returns maximum value for capacity C
static int max(int i, int j){
return (i > j) ? i : j;
}
static int knapSack(int C, int weight[], int value[], int n){
int i, c;
int K[][] = new int[n + 1][C + 1];
// creating table K[][] using bottom-up approach
for (i = 0; i <= n; i++){
for (c = 0; c <= C; c++){
if (i == 0 || c == 0)
K[i][c] = 0;
else if (weight[i - 1] <= c)
K[i][c]= max(value[i - 1]+ K[i][c - weight[i - 1]],K[i - 1][c]);
else
K[i][c] = K[i - 1][c];
}
}
return K[n][C];
}
// Driver code
public static void main(String args[]){
int value[] = new int[] { 25, 30, 15 };
int weight[] = new int[] { 15, 5, 10 };
int C = 100;
int n = value.length;
System.out.println(knapSack(C, weight, value, n));
}
}
You can also try this code with Online Java Compiler
There will be ‘N * C’ calls in a recursive function as we are using a 2D array, and if the value is present in this array, then we are not making duplicate calls. So there will be utmost N * C combinations. Therefore the overalltime complexityis O(N * C).
Space Complexity: O(N * C)
Though a 2D array is used array’s first dimension value is 2, which is constant, so, therefore, the overall space complexity is O(2 * C) = O(C).
You can also practice the unbounded knapsack problem here.
Applications of Knapsack algorithm
Knapsack algorithm is used in:
Home energy management
Radio networks
Resource management in software
Power allocation management
Solving the production planning problem
Optimizing power allocation to electrical appliances
Frequently Asked Questions
What are some problems related to unbounded knapsack?
Rod cutting, coin change (both for maximum and minimum), and maximum ribbon cut are some of the problems that are variations of the unbounded knapsack problem.
What is an unbounded knapsack?
The unbounded knapsack is the process of determining the most valuable collection of objects that can fit in a knapsack of a particular volume given several sorts of items of various values and volumes.
What is the best approach for an unbounded knapsack problem?
The goal of a knapsack problem is to maximize profit. Therefore, dynamic programming and branch are the better options in comparison to the greedy method.
What is the difference between an unbounded knapsack and a 0-1 knapsack?
The only difference between 0/1Knapsack and Unbounded Knapsack is that we may utilize an infinite number of items in this case.
What is a multiple knapsack problem?
This is a generalization of the standard knapsack problem from 1 to ‘M’ knapsacks which might have different capacities.
Conclusion
In this article, we learned about the solutions to unbounded knapsack problems and how the unbounded knapsack works with an example.
The unbounded knapsack problem is very efficient for cases where input values where the range of elements is wide. It is a subset of the dynamic programming topic. You can read more about this topichere.