[KUJustin]

The math part of my brain has really atrophied since high school. Let me give an example of the problem I'm thinking about and my proposed solution (which I've realized only approximates an answer). I'd be interested to hear how you guys would solve this, assuming it's solvable. I'm using a small set, but obviously the goal is a scalable solution.

[ QUOTE ]
You need to choose 1 food from each category to maximize your calories under a constraint of a $10 budget.

Main Dishes
Hamburger (400 cal) - $3
Sandwich (200 cal) - $1
Steak (500 cal) - $5

Side
Fries (150 cal) - $2
Corn (100 cal) - $1
A bowl of melted cheese (500 cal) - $4

Dessert
Pie (400 cal) - $3
Cake (350 cal) - $2
Boring Cookie (200 cal) - $1


[/ QUOTE ]

So we're trying to maximize calories/$. Let's assume given the economics of things if everyone has this goal, the highest calories/$ foods would also be the ones with the lowest calorie totals. I would imagine if this assumption isn't true and the highest cal/$ put you over budget you could use my solution in reverse.

My thoughts
What I would do is choose the highest cal/$ item from each category. In this case Sandwich, Corn, and Cookie are all 200/$ so I start there, but I have $7 going to waste. So I subtract the stats for each of these foods from the remaining available foods. So Hamburger becomes 200cal/$2, steak is 300cal/$4. Since I know I need to spend at least 1 more dollar, this gives me an incremental cals/$. I can choose from any category now since I've established a baseline in each one.

So I chose the next best cal/$ use of my money, reset the baselines, and do it again until I've maximized cals under the constraint.

2 problems with my solution:
1) It's an approximation. Say I've spent $6 and the next best incremental choice is an item that costs $3 more than the current baseline. It's possible that this is ideal or it's possible it's precluded me from getting 2 items for $2 extra that would be more optimal.

2) Though this approximation isn't exponential, it still could require as many iterations as you have items. And to correct the problem "1)" would turn it back to exponential I believe.

Okay, that's all I've got. Anxious to hear your response.