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 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.
Input: weight[] = {10, 20, 30}, value[] = {60, 100, 120}, n = 3, capacity = 50
Output: 300
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.
In the case of "unbounded knapsack," we may include an element multiple times.
It only differs from a 0/1 snapsack in the sense that, in 0/1, if an item is selected, we move to the next element (pass 'n-1' in recursive call), but in the case of an "unbounded knapsack", we do not move to the next element (do not pass 'n-1' in recursive call).
On the other hand, if an element is "not included", we move to the next element for both "0/1 or unbounded" (pass 'n-1' in recursive call).
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.