Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I received at my work some meal tickets valued at 8.80 euros a piece, and my wife who works at another firm, receives meal tickets at 7.50 euros a ticket. The neighborhood that we work at accepts these for food, but doesn't return change. When we go out together, we want to maximize the value of the tickets by arranging some combination of the meal tickets.

So my question is: what is the algorithm to determine the best value?

share|improve this question
1  
Is it feasible to pay for most of a meal with the tickets, and then pay the rest with real cash? If so, you wouldn't have to waste any money. Otherwise: unless there are hundreds of items on the menu, just looking at all of the appetizing combinations one-by-one shouldn't take too long. –  Lopsy Jan 11 '13 at 18:58
    
Here are the assumptions: you don't have another form of payment, so you will almost always have to pay more than the meal price. Second, although it is nice to have enough of a selection to get exactly the right combination of tickets, in practice this doesn't really work out. –  Mark McWhirter Jan 11 '13 at 19:02
    
Convince the restaurant to let you have a standing tab that is deducted against the tickets. (of course, this is not a 'math' solution) –  Calvin Lin Jan 11 '13 at 19:07
    
By the way, how much does the "average" meal cost? Or does it vary wildly depending on where you go? –  Lopsy Jan 11 '13 at 19:07
1  
maybe you can handle it this way xkcd.com/287 ;) –  sonystarmap Jan 11 '13 at 19:49
show 3 more comments

1 Answer

up vote 2 down vote accepted

The prices between 10 and 20 euros that you can exactly hit using combinations of 8.80-euro and 7.50-euro tickets are $15.00, 16.30,$ and $17.60$. Between 20 and 30 euros, there's $22.50, 23.80, 25.10,$ and $26.40$. So heuristically, if a meal is anywhere between 13.70 and 17.60 euros, or anywhere between 21.20 and 26.40 euros, then you won't be wasting more than 1.30 no matter what.

The exact formal problem - that is, finding a combination of menu items that exactly totals some amount - is known to be NP-Complete. In other words, it's hard, and there's essentially no better way to solve it than to look at every combination. There's some information about the theoretical problem on Wikipedia here. Fortunately, in a real restaurant, you have some saving graces. For example, there are usually a lot of items with the same price, so you don't have to do as much arithmetic. On top of that, you only look at combinations which you would actually order.

But in general, I'm afraid there's nothing much better than the approach you were probably already using, adding up various appetizing meals and seeing how many tickets they use. Remembering the target values - $15.00, 16.30,$ and $17.60$ on one end, $22.50, 23.80, 25.10,$ and $26.40$ on the other - should speed up the process, however.

Finally, and this is important, don't get caught in the tempting logical trap of thinking you're "wasting money" when you're not. If there's one meal that costs $15.01$ and a another meal that costs $16.30$ exactly, then sure it feels like the latter "wastes less money". But in the end, they both use one 7.50 ticket and one 8.80 ticket, so it doesn't matter - you should just pick whichever one is tastier.

share|improve this answer
1  
Thank you for the well thought out response! Great insight on the logical trap - now I don't have to try out the 'Anthrax Ripple' to get better value. –  Mark McWhirter Jan 11 '13 at 19:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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