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