Determining the maximum value 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?
 A: 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.
