**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 -

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.

So the answer will be 245 in this case.

Also See, __Byte Array to String__

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