0/1 Knapsack Problem
Problem
Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. In the 0/1 Knapsack problem, you can either take an item (1) or leave it (0).
Examples:
Example 1:
Input: values = [60, 100, 120], weights = [10, 20, 30], capacity = 50
Output: 220
Explanation: We can take items with values 100 and 120, with weights 20 and 30, for a total value of 220.
Example 2:
Input: values = [10, 40, 30, 50], weights = [5, 4, 6, 3], capacity = 10
Output: 90
Explanation: We can take items with values 40 and 50, with weights 4 and 3, for a total value of 90.
Solution
Intuition
- For each item, we have two choices: include it in the knapsack or exclude it.
- The naive approach would be to try all possible combinations of items, leading to an exponential time complexity of O(2^n).
- Dynamic Programming can optimize this by storing the results of subproblems to avoid redundant calculations.
- We can define a state DP[i][w] as the maximum value that can be obtained using the first i items with a maximum weight of w.
Approach
- Create a 2D array dp[n+1][W+1] where n is the number of items and W is the maximum weight capacity.
- Initialize the base case: dp[0][w] = 0 for all w (no items means no value) and dp[i][0] = 0 for all i (zero capacity means no value).
- For each item i and weight w, if the weight of item i is greater than w, we can't include it, so dp[i][w] = dp[i-1][w].
- Otherwise, we take the maximum of two cases: (a) excluding the item: dp[i-1][w], or (b) including the item: value[i-1] + dp[i-1][w-weight[i-1]].
- The final answer is dp[n][W], which represents the maximum value with n items and weight capacity W.
Complexity Analysis
- Time Complexity: O(n×W) - We fill a 2D table of size (n+1)×(W+1).
- Space Complexity: O(n×W) - We use a 2D array of size (n+1)×(W+1).
Implementation
CPP
Run your code to see output here