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.
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.