Knapsack Flashcards
(5 cards)
What is the 0/1 Knapsack pattern and when is it used?
Solves optimization using dynamic programming for item selection.
Use Case: Maximize value within capacity.
Example: [No LeetCode match, course example: Knapsack].
Action: Verbalize use case aloud.
What are the key steps for the 0/1 Knapsack?
- Create DP table for items and capacity.
- Fill table: max value including/excluding item.
- Return max value.
Action: Explain steps for Knapsack aloud.
How does the 0/1 Knapsack apply to Knapsack?
Maximize value of items within weight limit.
Approach: Use DP to compute max value for each capacity.
Example: Knapsack. Action: Verbalize solution logic aloud.
What are the complexity and gotchas of the 0/1 Knapsack?
Time: O(nW), Space: O(nW).
Gotchas: Zero capacity, no items.
Action: List edge cases for Knapsack aloud.
Code example for the 0/1 Knapsack.
```python
from typing import List
def knapsack(values: List[int], weights: List[int], capacity: int) -> int:
n = len(values)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
if weights[i-1] <= w:
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
else:
dp[i][w] = dp[i-1][w]
return dp[n][capacity]
~~~