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
|