Minimum Cost Combo: Select Item Combination at Lowest Total Price with Constraints

Question

## Problem

A menu has items each with a `name`, `category`, and `price`. A valid combo requires exactly one item from each required category. Given a list of required categories and all menu items, return the minimum total price of a valid combo. If no valid combo exists, return -1.

```python
def min_cost_combo(items: list[dict], required: list[str]) -> int:
    # items: [{"name": str, "category": str, "price": int}]
    pass
```

**Example:**
```
Items:
  {name:"Cola",  category:"drink", price:2},
  {name:"Water", category:"drink", price:1},
  {name:"Burger",category:"main",  price:8},
  {name:"Salad", category:"main",  price:6}

Required: ["drink", "main"]

Cheapest combo: Water(1) + Salad(6) = 7
Output: 7
```

## Follow-ups

1. What if some categories have a discount when combined (e.g., drink + main = 20% off)? How does this change your approach?
2. What if you must pick at least one item from each required category but can pick multiple from any?
3. For a menu with 10 categories and 50 items each, how do you avoid brute-force?
4. Model this as a dynamic programming problem. What are your states?

Minimum Cost Combo: Select Item Combination at Lowest Total Price with Constraints

Question Details

Full Details

Topics

More from Airbnb