A delivery app wants to show a customer all the cheapest ways to get the dishes they asked for. The restaurant's menu is a list of entries (id, price, items):
idis a unique integer,pricea positive integer;itemsis a comma-separated string of distinct dish names, e.g."burger"or"burger,fries,soda"for a combo.
The customer lists the dishes they want in wants (distinct names). An order is a set of menu entries (each entry at most once) whose items together include every wanted dish. Extra dishes are fine. Its cost is the sum of its prices.
Implement cheapest_orders(menu: list[tuple[int, int, str]], wants: list[str]) -> list[list[int]]: every order of minimum cost, each as a sorted list of ids, the whole list sorted. Return [] if no order covers wants, and [[]] if wants is empty.
menu = [
(1, 6, "taco"),
(2, 4, "soup"),
(3, 9, "taco,soup"),
(4, 11, "taco,soup,flan"),
(5, 2, "flan"),
(6, 5, "soup,flan"),
]
cheapest_orders(menu, ["taco", "soup"]) # [[3]] the combo (9) beats 6 + 4
cheapest_orders(menu, ["taco", "soup", "flan"]) # [[1, 6], [3, 5], [4]] all cost 11; [1, 2, 5] costs 12
cheapest_orders(menu, ["pie"]) # []
cheapest_orders(menu, []) # [[]]
Up to 12 wanted dishes and 50 menu entries, so trying every subset of the menu is out of the question.
Show hint
Only wanted dishes matter, so turn each entry into a bitmask over wants. Let best(rem) be the cheapest cost to cover the dishes in mask rem: some chosen entry must cover the lowest dish in rem, so try each such entry and recurse on what it leaves. Memoize it, then walk the same choices again, following only those that achieve best, to list the orders (collect them in a set, since one order can be reached along different paths).