I want to find an efficient algorithm for determining the minimum possible order total for a party of n people at a restaurant, assuming that the items in the order are unique, and they will each order one item, or will share items based on the recommended number of people for those items. e.g. a party of 3 may order a steak and a pizza if the pizza is listed as a 2-person item on the menu. I have an algorithm that seems to work well when there are only single-person items on the menu, but the multi-person items throw a wrench into it. Here's what I have so far:
- Order all items on the menu by increasing price.
- For a party of n, take the sum of the prices of the first n items.
My next idea was that as I'm adding each item I would check to see if there is a multi-person item with a lower cost than the total so far. This improves the algorithm, but does not take into account the possibility of having multiple multi-person items.