Gifts Knapsack (0/1 Maximize Importance)
You are choosing a subset of gifts to pack. Gift i has weight weights[i] and importance values[i] (both non-negative integers). The bag holds a total weight of at most capacity. Each gift may be taken at most once (0/1). Maximize the total importance of the packed gifts subject to the weight limit, and return that maximum total importance.
Complete: ``` knapsack(weights: List[int], values: List[int], capacity: int) -> int ``` Example: weights = [1, 3, 4, 5], values = [1, 4, 5, 7], capacity = 7 -> take gifts of weight 3 and 4 (importance 4 + 5 = 9) for a total of 9.
Hints
- 1-D DP over capacity: dp[c] is the best importance for a weight budget of c.
- Iterate capacity from high to low when adding each gift so it is counted at most once (0/1, not unbounded).
Worked Solution
Standard 0/1 knapsack DP. dp[c] = best importance achievable with total weight exactly at most c. For each gift (w, v), update capacities from high to low so each gift is used at most once: dp[c] = max(dp[c], dp[c - w] + v) for c from capacity down to w.
```python def knapsack(weights, values, capacity): dp = [0] * (capacity + 1) for w, v in zip(weights, values): for c in range(capacity, w - 1, -1): cand = dp[c - w] + v if cand > dp[c]: dp[c] = cand return dp[capacity] ```
Complexity $O(n \cdot capacity)$ time, $O(capacity)$ space.
Intuition
Each gift is an independent include/exclude decision; the rolling 1-D table caches, for every budget, the best importance using the gifts seen so far, and the reverse capacity loop prevents reusing a gift within the same pass.