Do you think IIT Guwahati certified course can help you in your career?
Introduction
This blog will discuss the various approaches to solving 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 the 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 -
Item
A
B
C
Value
80
110
135
Weight
15
20
35
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.
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 inRecursion 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)
// 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)
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 a 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).
Frequently asked questions
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 the 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 the items packed in the bag.
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.
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 the item with more value.
Conclusion
In this article, we discussed what is 0-1 Knapsack is, the various approaches to solving this problem programmatically, and 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, you can visit Coding Ninjas Studio.
34+ registered 
