A delivery app wants to tell a customer the cheapest way to get a set of dishes. The restaurant's menu is a list of entries (entry_id, price, items):
entry_idis a unique integer,priceis a positive integer (in cents),itemsis a comma-separated string of distinct item names, such as"burger"(a single dish) or"burger,fries,soda"(a combo). Names contain no commas and no surrounding spaces.
The customer lists the distinct items they want in wants. Implement
min_order_cost(menu: list[tuple[int, int, str]], wants: list[str]) -> int
returning the smallest total price of a set of menu entries whose items together include every wanted item. Extra, unwanted items in a combo are fine (the customer just gets them). Return -1 if some wanted item appears in no entry, and 0 if wants is empty.
menu = [
(1, 500, "burger"),
(2, 300, "fries"),
(3, 250, "soda"),
(4, 900, "burger,fries,soda"),
(5, 650, "burger,soda,cookie"),
]
min_order_cost(menu, ["burger", "fries", "soda"]) # 900 (the combo beats 500 + 300 + 250)
min_order_cost(menu, ["burger", "soda"]) # 650 (entry 5; the cookie is a bonus)
min_order_cost(menu, ["fries", "soda"]) # 550
min_order_cost(menu, ["fries", "salad"]) # -1
Constraints: len(wants) <= 12, len(menu) <= 300, each entry has at most 12 items, prices up to 10**6.
Picking the cheapest entry per item, or the best "price per wanted item", is not optimal. Trying every subset of the menu is far too slow with 300 entries.
Show hint
Number the wanted items 0..k-1 and turn each entry into a bitmask of the wanted items it contains (ignore the rest; drop entries with mask 0). Then best[mask] = cheapest cost to cover at least mask: start from best[0] = 0 and relax best[m | entry_mask] = min(..., best[m] + price) over masks in increasing order. Keeping only the cheapest entry per distinct mask speeds it up further.