In a knapsack problem, "n" items are given with their weight (weight[]) and value (value[]).
The task is to put these items in a "knapsack" of capacity W to get the maximum total value (profit) in the knapsack.
Two integer arrays, weight[0..n-1] and value[0..n-1] are given, which represent "values" and "weights" associated with "n" items, respectively.
Also, given an integer W, which represents knapsack capacity, find out the maximum value (profit) such that the sum of weights of picked items is smaller than or equal to W.
The 0/1 knapsack means that an item is either picked completely or not picked at all (no fraction by weight is allowed).
Input: weight[] = {10, 20, 30}, value[] = {60, 100, 120}, n = 3, capacity = 50
Output: 220
Input: weight[] = {1, 3, 4, 5}, value[] = {10, 40, 50, 70}, n = 4, capacity = 8
Output: 110
Solutions
Method 1: Memoization
The Memoization Technique is basically an extension to the recursive approach so that we can overcome the problem of calculating redundant cases and thus decrease time complexity.
We can see that in each recursive call only the value of "n" and "w" (capacity) changes, so we can store and reuse the result of a function(..n, w..) call using a "n * w" 2-D array.
The 2-D array will store a particular state (n, w) if we get it the first time.
Now, if we come across the same state (n, w) again, instead of calculating it in exponential complexity, we can directly return its result stored in the table in constant time.
Complexity
The time complexity of this solution is (n * w).
In addition, O(n * w) auxiliary space was used by the table.
Method 2: Recursion
The idea of the recursive approach is to consider all subsets of items whose total weight is smaller than or equal to W and pick the maximum value subset.
While considering an item, we have one of the following two choices:
Choice 1: The item is included in the optimal subset—decrease the capacity by the item weight and increase the profit by its value.
Choice 2: The item is not included in the optimal set—don't do anything.
While picking an element, also make sure that the weight of the item is less than or equal to the remaining capacity of the knapsack.
Complexity
The above recursive function computes the same sub-problems again and again.
The time complexity of this solution is exponential (2^n).
In addition, O(N) auxiliary stack space was used for the recursion stack.