Knapsack Dynamic Programming
The Knapsack dynamic programming pattern is used to solve problems where items have certain values and weights, and we aim to maximize the value of items included in a knapsack (or a backpack) with a given capacity.
In this pattern, we define a 2D array dp[i][w]
to store the maximum value that can be achieved using the first i
items and a knapsack capacity of w
. We then iteratively fill in this array to compute the final answer.
Top-Down Approach:
1 2 3 4 5 6 7 8 9 10 |
|
Bottom-Up Approach:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
Complexity:
-
Time Complexity: The time complexity of both top-down and bottom-up approaches is \(O(nW)\), where \(n\) is the number of items and \(W\) is the capacity of the knapsack.
-
Space Complexity: The space complexity is determined by the size of the DP array, which is typically \(O(nW)\).