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