A Math Problem (NP Complete?)

[m_the0ry]

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.

[KUJustin]

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.

[m_the0ry]

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.

[KUJustin]

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.

[m_the0ry]

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.

[KUJustin]

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

[LondonBroil]

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

[br.bm]

why do you guys try to solve this problem?