Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction to Unbounded Knapsack
2.
What are knapsack problems?
2.1.
Types of Knapsack
2.1.1.
Fractional Knapsack 
2.1.2.
0-1 Knapsack
2.1.3.
Unbounded Knapsack 
3.
Recursive Approach for Unbounded Knapsack
3.1.
Algorithm
3.2.
Code Snippet
3.3.
Complexity Analysis
4.
Dynamic Programming: Top-down Approach
4.1.
Algorithm
4.2.
Code Snippet
4.3.
Complexity Analysis
5.
Bottom-Up Approach for Unbounded Knapsack
5.1.
Algorithm
5.2.
Code Snippet
5.3.
Complexity Analysis
5.4.
Applications of Knapsack algorithm
6.
Frequently Asked Questions
6.1.
What are some problems related to unbounded knapsack?
6.2.
What is an unbounded knapsack?
6.3.
What is the best approach for an unbounded knapsack problem?
6.4.
What is the difference between an unbounded knapsack and a 0-1 knapsack?
6.5.
What is a multiple knapsack problem?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Unbounded Knapsack

Author Reet Maggo
6 upvotes

Introduction to Unbounded Knapsack

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.

(Also see Data Structures)

unbounded knapsack

 

Also See, Byte Array to String

What are knapsack problems?

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
  • The Constraint is the weight (usually denoted by ‘W’ or ‘C’)
knapsack illustration

Source: en.wikipedia.org

Types of Knapsack

Fractional Knapsack 

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
Run Code

Output

600
You can also try this code with Online Java Compiler
Run Code

Complexity Analysis

Time Complexity: O(2 ^ N)

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).

Also check out - Rod Cutting Problem

Dynamic Programming: Top-down Approach

Another approach for unbounded knapsack is the dynamic 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. 

unbounded knapsack recursion tree

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
Run Code

Output

Maximum value that the knapsack can have is : 600
You can also try this code with Online Java Compiler
Run Code

Complexity Analysis

Time Complexity: O(N ^ C)

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 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).

Read More - Time Complexity of Sorting Algorithms

Bottom-Up Approach for Unbounded Knapsack

Algorithm

  • 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
Run Code

Output

600
You can also try this code with Online Java Compiler
Run Code

Complexity Analysis

Time Complexity: O(N * C)

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 overall time complexity is 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:

  1. Home energy management
  2. Radio networks
  3. Resource management in software
  4. Power allocation management
  5. Solving the production planning problem
  6. 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 topic here. 

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. as well as some Contests and some more Interview Experiences curated by top Industry Experts only on  Coding Ninjas Studio.

Cheers!

Live masterclass