A Math Problem (NP Complete?)

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

[bluesbassman]

It is trivial to solve this problem by simply "checking" every allowable food subset (i.e. every set which contains exactly one item from each group), and choose the subset which provides the highest number of calories which satisfies the constraint.

Or are you looking for a solution more efficient than that? You aren't clear in your post.

[KUJustin]

Sorry, I should have emphasized that part; I'm looking for something scalable. Say 10 categories with 1,000 items each which would be an overwhelming number of combos.

[gumpzilla]

This looks like a minor variant on the knapsack problem, which I'm pretty sure is indeed NP complete. (EDIT: There's almost certainly some subtlety here, but with that name I bet there's a lot of literature out there that you can read up on.)

[bluesbassman]

By "scalable," do you mean the solution steps increase in polynomial time with increasing number of categories and items per category?

Also, can we make the following assumption:

Given any two items X and Y within a group, does

carlories(X) >= calories(Y) imply price(X) >= price(Y)?

[_Z_]

[ QUOTE ]
This looks like a minor variant on the knapsack problem, which I'm pretty sure is indeed NP complete. (EDIT: There's almost certainly some subtlety here, but with that name I bet there's a lot of literature out there that you can read up on.)

[/ QUOTE ]

I believe the 0-1 knapsack problem can be reduced to the OP problem. For each item in the knapsack problem, make it into a single item category. Then put a 0 calorie/$0 item in each category.

Solving the OP problem, in this case, is equivalent to solving the knapsack problem.

Since the knapsack problem is NP-hard, the OP problem is NP-hard. So no polynomial time algorithm exists (assuming no major breakthrough in mathematics).

Z

[KUJustin]

[ QUOTE ]
By "scalable," do you mean the solution steps increase in polynomial time with increasing number of categories and items per category?

[/ QUOTE ]

yes

[ QUOTE ]
Also, can we make the following assumption:

Given any two items X and Y within a group, does

carlories(X) >= calories(Y) imply price(X) >= price(Y)?

[/ QUOTE ]

no

Given that this is "np-hard" is there a better solution for approximating than the one I've given? I'm going to research this based on the links and problem name provided, but if anyone has some more insight I'm obviously interested.

[jay_shark]

First , it helps to reduce the problem by dividing the number of calories by the $ amount with a common base .

Main Dishes
Hamburger 133.33:1
Sandwich 200 :1
Steak 100:1

Side
Fries 75:1
Corn 100:1
A bowl of melted cheese 125:1

Dessert
Pie 133.33:1
Cake 175:1
Boring Cookie 200:1


So if our goal is to select at least one from each catogory (not sure if that's what you mean), then we would prefer a sandwhich, melted cheese ,and a cookie . Now check to see that one of each selection is under $10 which it is since the total 1+4+1 = 6 . Since we are indifferent to a sandwhich or a cookie we may choose any combination such that s+c=6 and s and c are non-zero . So 5 cookies , one sandwhich and a bowl of melted cheese gives you 1700cal:$10 = 170:$1

[KUJustin]

I really didn't emphasize some of the finer points very well. I apologize.

You can only choose 1 from each category. Suppose it's a store with 1 of each in stock.

[jay_shark]

You still would choose one sandwhich , a bowl of melted cheese and a cookie .

Each of these 3 have the highest calories /$ for each catogory .

200:1 is higher than any other ratio under the main dish catogory .
125:1 is higher than any other ratio under the side category
200:1 is higher than any ratio under the dessert catogory .

I must be misinterpreting something because this is too easy .