Question: The Sushi Express wants to implement a new feature, order batching. The menu consists of a set of desired food items F and a set
The Sushi Express wants to implement a new feature, "order batching." The menu consists of a set of desired food items F and a set of combos c1, ..., cn where each combo is a set of food items along with a price - we represent combo ci = ({fi1, fi2, . . . , fik}, pi), where each fij is a food item in the combo. If a student orders ci, they receive each of the food items, and they pay the cost pi. In the new order batching system, the students would input a list of food items that they want, and the order batching system should find the cheapest set of combos, which would include at least one of each desired food item. Write the decision version of this problem, and show via reduction that this decision problem is NP Hard
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
