Unbounded Knapsack

Reet Maggo
Last Updated: May 26, 2022
Difficulty Level :
MEDIUM

Introduction to 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. 

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.

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

                                               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.

Recursive Approach for Unbounded Knapsack

Algorithm

  • First, the maximum value in the unbounded knapsack is returned by the function ‘max()’ using 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[] { 253015 };

        int weight[] = new int[] { 15510 };

        int C = 100;

        int n = value.length;

 

        System.out.println(knapSack(C, weight, value, n));

    }

}

Output

600

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

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. 

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[] { 253015 };

        int wt[] = new int[] { 15510 };

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

      }

}

Output

Maximum value that the knapsack can have is : 600

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

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[] { 253015 };

        int weight[] = new int[] { 15510 };

        int C = 100;

        int n = value.length;

        System.out.println(knapSack(C, weight, value, n));

    }

}

 

Output

600

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. You can also visit CodeStudio and try solving problems. 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think