Python Program for 0-1 Knapsack Problem using Recursion
A simple solution is to consider all subsets of items and calculate the total weight and profit of all subsets. Consider the only subsets whose total weight is smaller than W. From all such subsets, pick the subset with maximum profit.
Optimal Substructure: To consider all subsets of items, there can be two cases for every item.
- Case 1: The item is included in the optimal subset.
- Case 2: The item is not included in the optimal set.
Step-by-step approach:
The maximum value obtained from ‘N’ items is the max of the following two values.
- Case 1 (include the Nth item): Value of the Nth item plus maximum value obtained by remaining N-1 items and remaining weight i.e. (W-weight of the Nth item).
- Case 2 (exclude the Nth item): Maximum value obtained by N-1 items and W weight.
- If the weight of the ‘Nth‘ item is greater than ‘W’, then the Nth item cannot be included and Case 2 is the only possibility.
Below is the implementation of the above approach:
Python
# A naive recursive implementation # of 0-1 Knapsack Problem # Returns the maximum value that # can be put in a knapsack of # capacity W def knapSack(W, wt, val, n): # Base Case if n == 0 or W == 0: return 0 # If weight of the nth item is # more than Knapsack of capacity W, # then this item cannot be included # in the optimal solution if (wt[n-1] > W): return knapSack(W, wt, val, n-1) # return the maximum of two cases: # (1) nth item included # (2) not included else: return max( val[n-1] + knapSack( W-wt[n-1], wt, val, n-1), knapSack(W, wt, val, n-1)) # end of function knapSack # Driver Code if __name__ == '__main__': profit = [60, 100, 120] weight = [10, 20, 30] W = 50 n = len(profit) print knapSack(W, weight, profit, n) # This code is contributed by Nikhil Kumar Singh |
220
Time Complexity: O(2N)
Auxiliary Space: O(N), Stack space required for recursion
Python Program for 0-1 Knapsack Problem
Write a Python program for a given N items where each item has some weight and profit associated with it and also given a bag with capacity W, [i.e., the bag can hold at most W weight in it]. The task is to put the items into the bag such that the sum of profits associated with them is the maximum possible.
Examples:
Input: N = 3, W = 4, profit[] = {1, 2, 3}, weight[] = {4, 5, 1}
Output: 3
Explanation: There are two items which have weight less than or equal to 4. If we select the item with weight 4, the possible profit is 1. And if we select the item with weight 1, the possible profit is 3. So the maximum possible profit is 3. Note that we cannot put both the items with weight 4 and 1 together as the capacity of the bag is 4.Input: N = 3, W = 3, profit[] = {1, 2, 3}, weight[] = {4, 5, 6}
Output: 0