News for hackers. Stuff that matters.
Re:A CP Solution for XKCD NP Complete Restaurant Order by graycat on Tuesday May 28, 2013 @11:57AM (#5780755)
His restaurant problem is a special case of the knapsack problem where we have some items to carry, a value of each, and a weight of each, and a knapsack with a maximum weight we can carry, and we want to know what items to put in the knapsack to maximize the value but not exceed the maximum weight.

For the restaurant problem, for each item on the menu, just set both the value and the weight to the price, and for the maximum weight of the knapsack just use the budget.

Now, knapsack problems are in NP-complete, as I recall, but they are, in practice, among the easiest to solve. The usual recommendation for solving a large knapsack problem is via dynamic programming.

There are no comments on this comment yet.