0-1 Knapsack

Harsh Goyal
Last Updated: May 27, 2022

Introduction-  

This blog will discuss the various approaches to solve the 0-1 Knapsack problem. Before jumping into the problem, let’s first understand what a Knapsack problem is and then understand what 0-1 Knapsack is?

Knapsack simply means bag. A bag of given capacity. We have to pack ‘N’ items into this bag, and every item has some weight and value. We have to make sure the total weight of items is less than or equal to the weight that a bag can hold. At the same time, we have to maximize the value of items packed in the bag. 

This is the basics of the Knapsack problem. Now 0-1 Knapsack says you can either take the item as a whole or not, but you cannot break the item and take some part of it.

Let’s try to understand it with an example -

Max Weight knapsack can handle - 60

Below are 3 items along with their values and weight -

ItemABC
Value80110135
Weight152035

 

In this case, if we carry items B and C in a bag, the total weight will be 20 + 35 = 55, which is less than 60, and the total value will be 110 + 135 = 245.

So the answer will be 245 in this case.

Brute Force Approach - 

Brute Force Solution considers all subsets of items and picks the subset with a maximum value, and the weight of that subset is less than the knapsack weight.

To consider items in that optimal subset, there are 2 ways in front of us -

  • Either we consider the item in that set.
  • Or we don’t consider the item in that set.

While considering an item in the set, we have to ensure its weight is less than the weight knapsack can hold.

Hence, we have to consider the maximum value of

  • ‘N - 1’ items and ‘W’ weight by excluding Nth item
  • ‘N - 1’ items and ‘W - Nth’ item Weight

Algorithm -

Step 1. Create a recursive function ‘getMaximumKnapsackValue()’ that will accept the below parameters -

  • ‘W’ - the weight of knapsack, ‘values’ - an array of item values, ‘weight’ - an array of item weights, ‘N’ - number of items

Step 2. Check if the weight of the ‘Nth’ item is more than the current weight ‘W’, then recursively call the same function ‘getMaximumKnapsackValue()’ for ‘N - 1’ items and ‘W’ weight and return the result ‘maxValue’.

Step 3. Else call recursive function for ‘N - 1’ and ‘W’ - weight[n] and for ‘N - 1’ items with ‘W' weight and return the maximum of step 5 and step 6 i.e., ‘maxValue’.

 

public class Solution {

 

    private int getMaximumKnapsackValue(int w, int weight[], int values[], int n)

    {     

        

        // Base Case

        if (n == 0)

        {

            return 0;

        }

 

        // Base Case

        if (w == 0)

        {

            return 0;

        }

 

        // If weight is more than the current knapsack weight, then we have to exclude this item

        if (w < weight[n - 1])

        {

         int maxValue = getMaximumKnapsackValue(w, weight, values, n - 1);

         return maxValue;

        }

        else

        {

         // Pick Nth item and add its value in result

         int valueWithNthItem = getMaximumKnapsackValue(w - weight[n - 1], weight, values, n - 1) +  values[n - 1];

        

         // Exclude Nth item and go for N - 1 items

         int valueWithoutNthItem = getMaximumKnapsackValue(w, weight, values, n - 1);

        

         // Get the maximum of both values

         int maxValue = Math.max(valueWithNthItem, valueWithoutNthItem);

        

         return maxValue;

        }

       

    }

 

 

    public static void main(String[] args) 

    {

 

      Solution solution = new Solution();

      int val[] = new int[] { 80, 110, 135 };

      int wt[] = new int[] { 15, 20, 35 };

      int W = 60;

      int n = val.length;

        

      int maxValue = solution.getMaximumKnapsackValue(W, wt, val, n);

        

      System.out.println("Maximum value that Knapsack can have is : " + maxValue);

    }

}

Output :

 

Maximum value that Knapsack can have is: 245

 

Algorithm Complexity: 

Time Complexity: O(2 ^ N)

In every recursive call ‘getMaximumKnapsackValue()’, we are making 2 more calls to the same function so calls are increasing at a rate of 2 until ‘N’ or ‘W’ reaches 0. There will be at most ‘2 ^ N’ calls in this code. Therefore the overall time complexity will be O(2 ^ N).

Space Complexity: O(1)

As we are using constant space. Therefore the overall space complexity will be O(1).

Top-Down Approach -

In the above approach, there are a lot of duplicate calls for the same state ‘N’ and ‘W’, which is leading to exponential complexity. For high ‘N’ and ‘W’. the above algorithm will run forever.

We can avoid calling a recursive function by using an array and storing the state in that array. If we encounter the same state again during execution, we will return from the array instead of recomputing again. This approach will drastically decrease the time complexity. 

 

                                                     Source: IDeserve

Algorithm -

Step 1. Create a function and initialize the 2D array of size (N + 1) * (W + 1) and call the recursive function ‘getMaximumKnapsackValue()’ which accepts below parameters -

  • ‘W’ - the weight of knapsack; ‘values’ - an array of item values, ‘weight’ - an array of item weights, ‘N’ - number of items

Step 2. Base case will be if N = 0 or W = 0 then return 0. 

Step 3. Check if the value is present in the array. If yes, then return it.

Step 4. Check if the weight of the ‘Nth’ item is more than the current weight ‘W’ then recursively call the same function ‘getMaximumKnapsackValue()’ for ‘N - 1’ items and ‘W’ weight, assign it to array[N][W] return the result.

Step 5. Else get the maximum of step 5 and step 6 and assign the result to array[N][W] and return it.

Step 6. call recursive function ‘getMaximumKnapsackValue()’ for ‘N - 1’ and ‘W’ - weight[N].

Step 7. call the recursive function ‘getMaximumKnapsackValue()’ for ‘N - 1’ items with ‘W’ weight.

 

public class Solution {

 

    int getMaximumKnapsackValue(int w, int weight[], int values[], int n, int[][] arr)

    {     

  // Base Case

        if (n == 0)

        {

            return 0;

        }

 

        // Base Case

        if (w == 0)

        {

            return 0;

        }

 

        if (arr[n][w] != -1)

        {

            return arr[n][w];

        }

 

        // If weight is more than current knapsack weight then we have to exclude this item

        if (w < weight[n - 1])

        {

         int maxValue = getMaximumKnapsackValue(w, weight, values, n - 1,arr);

         arr[n][w] = maxValue;

         return maxValue;

        }

        else

        {

         // Pick Nth item and add its value in result

         int valueWithNthItem = getMaximumKnapsackValue(w - weight[n - 1], weight, values, n - 1, arr) + values[n - 1];

        

         // Exclude Nth item and go for n-1 items

         int valueWithoutNthItem = getMaximumKnapsackValue(w, weight, values, n - 1, arr);

        

         // Get the maximum of both values

         int maxValue = Math.max(valueWithNthItem, valueWithoutNthItem);

        

         arr[n][w] = maxValue;

        

         return maxValue;

        }

    }

 

    int getMaximumKnapsack(int w, int weight[], int values[], int n)

    { 

       // Initialize 2D array of size N + 1 and w + 1 with value -1

        int arr[][] = new int[n + 1][w + 1];

 

        for(int i = 0; i < n + 1; i++)  

        {

         for(int j = 0; j < w + 1; j++)  

         {

         arr[i][j] = -1;   

         }

        }

        return getMaximumKnapsackValue(w, weight, values, n, arr);    

    }

    

public static void main(String[] args) 

{

        Solution solution = new Solution();

        int val[] = new int[] { 80, 110, 135 };

        int wt[] = new int[] { 15, 20, 35 };

        int W = 60;

        int n = val.length;

        

        int maxValue = solution.getMaximumKnapsack(W, wt, val, n);

        

        System.out.println("Maximum value that Knapsack can have is : " + maxValue);

 

}

}

Output :

Maximum value that Knapsack can have is : 245

 

Algorithm Complexity: 

Time Complexity: O(N * W)

There will be ‘N * W’ 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 * W combinations. Therefore the overall time complexity is O(N * W).

Space Complexity: O(N * W)

As we are using a 2D array of size ‘N * W’. Therefore the overall space complexity is O(N * W).

Bottom-Up Approach -

In the above approach, there is the overhead of the internal stack being used in recursion and we can eliminate it by using an iterative approach. We will take a 2D array and will start populating it from the bottom ( 0th index ) to top ( Nth index ) hence by using this approach, we can make our algorithm more memory efficient. 

Algorithm -

Step 1. Create a function that will accept the below parameters -

  • ‘W‘ - the weight of knapsack, ‘values’ - an array of item values, ‘weight’ - an array of item weights, ‘N’ - number of items

Step 2. Run an outer for loop with index ‘i’ varying from 0 to ‘N’.

Step 3. Run an inner for loop with index ‘j’ varying from 0 to ‘W’

Step 4   If i = 0 or j = 0 then the state value will be 0 because the answer will be 0 if weight (‘j’) is 0 or no items (‘i’) is there.

Step 5. If the weight of ‘ith’ item > current weight ‘j’ then exclude ith item and pick the value of arr[i - 1][j] 

Step 6. Else pick a maximum of array’s value with or without ith item.

 

public class Solution {

 

    int getMaximumKnapsackValue(int w, int weight[], int values[], int n)

    {     

  // Initialize 2D array 

        int array[][] = new int[n + 1][w + 1];

 

        for (int i = 0; i <= n; i++)

        {

            for (int j = 0; j <= w; j++)

            {

               // Base case

                if (i == 0 || j == 0)

                {

                 array[i][j] = 0;

                }

                else if (weight[i - 1] <= j)

                {

                 // Max of including or excluding item 

                 int val1 = values[i - 1] + array[i - 1][j - weight[i - 1]];

                 int val2 = array[i - 1][j];

                 array[i][j] = Math.max(val1,val2);

                }

                else

                {

                 // Exclude item if weight is more than current weight

                 array[i][j] = array[i - 1][j];

                }

            }

        }

 

        return array[n][w];

    }

    

 

public static void main(String[] args) 

{

 

        Solution solution = new Solution();

        int val[] = new int[] { 80, 110, 135 };

        int wt[] = new int[] { 15, 20, 35 };

        int W = 60;

        int n = val.length;

        

        int maxValue = solution.getMaximumKnapsackValue(W, wt, val, n);

        

        System.out.println("Maximum value that Knapsack can have is : " + maxValue);

}

}

 

Output :

Maximum value that Knapsack can have is : 245

 

 

Algorithm Complexity: 

Time Complexity: O(N * W)

There will be at ‘N * W’ calls in a 2D array using the nested ‘for’ loop. Therefore the overall time complexity is O(N * W).

Space Complexity: O(N * W)

As we are using a 2D array of size ‘N * W’. Therefore the overall space complexity is O(N * W).

Optimized Approach -

If we look closely at the above approach, we will notice that we are only using 2 rows in a 2D array: one current row and one previous row. We are not using anything other than these 2 rows, so it would be better to initialize a 2D array with 2 rows instead of n rows. It will reduce the space complexity to much extent.

Algorithm -

Step 1. Create a function that will accept the below parameters -

  • ‘W’ - the weight of knapsack, ‘values’ - an array of item values, ‘weight’ - an array of item weights, ‘N’ - number of items

Step 2. Create a 2D array of size ‘2 * W’.

Step 2. Run an outer for loop with index ‘i’ varying from 0 to N.

Step 3. Run an inner for loop with an index varying from 0 to W.

Step 4 If ‘i’ is even, then use array’s 1st row else ‘0th’ row.

Step 5. If the weight of the ‘ith’ item is higher than the current weight, exclude this item else,  take the maximum value by including and excluding the item. 

Step 6. Return the result.

 

public class Solution1 {

    int getMaximumKnapsackValue(int w, int weight[], int values[], int n)

    {     

  // Initialize 2D array 

        int array[][] = new int[2][w + 1];

 

        for (int i = 0; i < n; i++)

        {

           for (int j = 0; j <= w; j++)

           {

             // If i is even then use 1th row

             if(i % 2 == 0)

             {

             // Exclude weight

             if(weight[i] > j)

                 {

                 array[0][j] = array[1][j];

                 }

             else

             {

             array[0][j] = Math.max(array[1][j], array[1][j-weight[i]] + values[i]);

             }

             }

             else    // If i is odd, then use 0th row

             {

             // exclude weight

             if(weight[i] > j)

                 {

                 array[1][j] = array[0][j];

                 }

             else

             {

             array[1][j] = Math.max(array[0][j], array[0][j-weight[i]] + values[i]);

             }

             }

           }

        }

 

        if(n % 2 == 0)

        {

         return array[1][w];

        }

        else

        {

         return array[0][w];

        }

     }

    

public static void main(String[] args) 

{
 

        Solution1 solution = new Solution1();

        int val[] = new int[] { 80, 110, 135 };

        int wt[] = new int[] { 15, 20, 35 };

        int W = 60;

        int n = val.length;

        

        int maxValue = solution.getMaximumKnapsackValue(W, wt, val, n);

        

        System.out.println("Maximum value that Knapsack can have is : " + maxValue);

 

}

}

Output :

Maximum value that Knapsack can have is : 245

 

 

Algorithm Complexity: 

Time Complexity: O(N * W)

There will be ‘N * W’ calls in a 2D array using the nested ‘for’ loop. Therefore the overall time complexity is O(N * W).

Space Complexity: O(W)

Though 2D array is used array’s first dimension value is 2, which is constant, so, therefore, the overall space complexity is O(2 * W) = O(W).

 

Check out this video tutorial to understand it better.

Frequently asked questions-

1) What is the Knapsack Problem?

Knapsack simply means bag ‘A’ of a given capacity. We have to pack ‘N’ items into this bag, and every item has some weight and value. We have to make sure the total weight of items is less than or equal to the weight that a bag can hold. At the same time, we have to maximize the value of items packed in the bag. 

2) What is 0-1 Knapsack?

0-1 Knapsack says you can either take the item as a whole or not, but you cannot break the item and take some part of it.

3) Can items with the same weights be present in the list?

Items with the same weight and different values can be present in the list, in that case, we have to pick that item with more value.

Key takeaways-

In this article, we discussed What is 0-1 Knapsack, discussed the various approaches to solve this problem programmatically, and discussed the time and space complexities. We find out how to use extra space and drastically reduce the time complexity from exponential to polynomial. Later, we find out different ways to reduce space complexity. If you want to practice more problems, then you can visit codestudio.

If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.



 

By Harsh Goyal
 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think