Item Selection: Select the Maximum Value Subset Under a Weight Constraint (0/1 Knapsack)

Question

## Problem

Given a list of items each with a weight and a value, and a maximum weight capacity, select a subset of items (each used at most once) to maximize total value without exceeding the capacity. Return the selected items and the total value.

```python
def item_selection(
    items: list[dict],  # [{"name": str, "weight": int, "value": int}]
    capacity: int
) -> tuple[list[str], int]:  # (selected_names, total_value)
    pass
```

**Example:**
```
items = [
  {"name": "A", "weight": 2, "value": 6},
  {"name": "B", "weight": 3, "value": 10},
  {"name": "C", "weight": 4, "value": 12},
  {"name": "D", "weight": 5, "value": 13},
]
capacity = 7
-> (["B", "C"], 22)   # weight=7, value=22
```

## Follow-ups

1. Walk through the DP table construction. What is the time and space complexity?
2. How do you reconstruct the selected items from the DP table (trace back)?
3. What changes if items can be used unlimited times (unbounded knapsack)?
4. If weights are very large (e.g., up to 10^9) but values are small, what alternative approach avoids the O(n * W) DP?

Item Selection: Select the Maximum Value Subset Under a Weight Constraint (0/1 Knapsack)

Question Details

Full Details

Topics

More from Uber