A Math Problem (NP Complete?)
 

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.

Re: A Math Problem (NP Complete?)
 

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.

Re: A Math Problem (NP Complete?)
 

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.

Re: A Math Problem (NP Complete?)
 

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

Re: A Math Problem (NP Complete?)
 

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)?

Re: A Math Problem (NP Complete?)
 

[ 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

Re: A Math Problem (NP Complete?)
 

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

Re: A Math Problem (NP Complete?)
 

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

Re: A Math Problem (NP Complete?)
 

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.

Re: A Math Problem (NP Complete?)
 

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 .

Re: A Math Problem (NP Complete?)
 

You can't generalize with the "highest cal/$ for each category" because of the $10 budget restriction. Take the following example:

type1:
fooda - 500cal,$4
foodb - 600cal,$4.01
type2:
foodc - 800cal, $6
foodd - 992cal, $6
foode - 500cal, $7

You might think of this as an extreme example but I guarantee that when the number of categories rises and the number of entries in each category rises, this kind of counterexample will become more and more prevalent.

The only addition to an exhaustive permutation search to optimize this is to remove an entry that shares the *exact* same cost as another entry but has a lower cal. For example we can remove foodc safely because there is no conceivable situation where we would replace foodd with foodc.

With few exceptions, when a minimum/maximum problem is to be found using a limited amount of resources it will be a non polynomial time problem. This means that we must exhaustively calculate all possibilities or permutations and check for the minimum/maximum.

Re: A Math Problem (NP Complete?)
 

Ok, I'm trying to meet people halfway, but you've got to read the problem.

Getting the highest cal/$ is where I started my solution from. The problem with that is the goal is to maximize calories, not cal/$. I'm pretty sure my solution is a viable approximation, though m_the0ry's example is a situation in which it would probably have a pretty significant error. Though if we're working with thousands of items and choosing 10 that effect should be reduced.

Re: A Math Problem (NP Complete?)
 

I think I convoluted my point a little bit too much in my last post,

The only way to solve this problem is by calculating every possible combination and finding the maximum. It is an NP complete problem. The approximation becomes worse as more items are added because more loss of information occurs.

Re: A Math Problem (NP Complete?)
 

m_the0ry, could you give me some insight on the problems with my idea for approximating this? My instinct is telling me it should get me pretty close, but I'm way out of my area here.

Re: A Math Problem (NP Complete?)
 

Sorry I didn't really answer your OP's question...

First to clarify the problem, you want to maximize calories with using at least 1 item from each category with the total cost <$10.

My question is why you subtract the stats of the highest cal/$ item from the rest. I was assuming that the prices and calories listed are of the lowest denomination. I think I'm not understanding some critical part of your algorithm here. A few potential problems arise from this step because we can very easily corrupt our data. For example you would commonly get a negative cal, negative price, or both, or even worse a divide by zero. This really messes with the algorithm and the way it does comparison. If we have an item with a good ratio but low stats, it will be quickly corrupted by this process (66cal for $.33 for example) but any time the best ratio item has more calories or more cost associated with it than another, something bad will happen.

Re: A Math Problem (NP Complete?)
 

m_the0ry, the constraint is ONLY 1 from each category. So the negative numbers would work with that in that those would be rejected. We'd want the maximum incremental cal/$.

Re: A Math Problem (NP Complete?)
 

Hamburger, bowl of cheese, and pie. I ARE TEH SMART!

Re: A Math Problem (NP Complete?)
 

why do you guys try to solve this problem?