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:

  1. Order all items on the menu by increasing price.
  2. 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.

  • $\begingroup$ What is the algorithm that seems to work well when there are only single-person items on the menu? $\endgroup$ – Jeffrey Young Oct 8 '14 at 15:53
  • $\begingroup$ The one I described in 2 steps above. Order all items on the menu by increasing price and just take the sum of the prices of the first n items for a party of n. $\endgroup$ – regularmike Oct 8 '14 at 15:59

If the number of people fed per item is not bounded above by a fixed constant, this is an NP-hard problem (i.e. it's almost guaranteed no fast solution exists). To see this, assume that you have $N$ people and you have a very expensive item that feeds $N$ people, and then you have a collection of very cheap multi-person items where the $i$th multi-person item serves $a_i$ people. Then ideally you want to find a subset of the cheap multi-person items such that $\sum_i a_i = N$ for the cheap multi-person items $i$ chosen in the subset. However that is the subset sum problem, which is NP-hard. So your problem is NP-hard. If you like, I can give you a pretty fast so-called dynamic programming solution assuming that the maximum number of people that an item can feed is bounded above by a fixed constant. Or you can read about it yourself, your problem is equivalent to the so-called "knapsack problem", e.g. you can read about on wikipedia and see the so-called dynamic programming solution.

  • $\begingroup$ This was more or less my suspicion, but I didn't know exactly how to show that it reduced to the subset sum problem. I'm somewhat familiar with NP-hard problems from college CX days, and I have come across the knapsack problem already while working on this project. Thanks. $\endgroup$ – regularmike Oct 8 '14 at 16:28

Assume you have soved the problem for all $n$ and a certain menu. Now assume that a new $k$-person dish at cost $c$ is added to the menu. Then the new optimum for $n$ persons is either the same as with the old menu, or it is the optimum for $n-k$ persons under the old menu plus $c$. This allows you to find the optimum for $N$ people and $M$ dishes in $O(NM)$ steps using $O(N) $ memory:

  1. Set $f[0]\leftarrow 0$ and $f[i]\leftarrow+\infty$ for $1\le i\le N$
  2. For $i=1,2\ldots, M$ do the following:
  3. For $j=N,N-1,\ldots,k[i]$, assign $f[j]\leftarrow\min\{f[j],f[j-k[i]]+c[i]\}$, where $k[i]$ is the person-count and $c[i]$ is the cost of the $i$th item on the menu
  4. Finally, $f[N]$ contains the answer.
  • $\begingroup$ I think I follow that, but this seems like a slightly different problem since you're just talking about adding one item to an existing menu where we already have answers for all n. $\endgroup$ – regularmike Oct 8 '14 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.