Algorithm for finding best combination of elements Say I have a very large, arbitrary number of variables, each of which I can assign to be type A, B, or C.

The types come with expenses: Type A's are the least expensive, and C's are the most expensive, but their expense varies from variable to variable.
For example {A, C, C} may actually be more expensive than {C, A, A} if that first variable happens to be worth more, but we won't know how much the total cost is until we assign the types and run the program. 

Also we don't want to go below a certain given total expense (can't make all A's), but get as close as possible to it.

I am trying to minimize the total expense while staying above the threshold. The search space (permutations of variable types) is too large to try all combinations.

Someone recommended sampling via Monte Carlo method earlier.
How can the Monte Carlo method, or Markov-Chain Monte Carlo, be applied to such a problem to find the optimal combination of parameters?
Could a genetic algorithm be used effectively?
You normally need to know what heuristic function you have.

Usually, when you use simulated annealing, you don't find a maximum score (or combination that gives the maximum score). What you do is trying to get a score that is better than the current score that you have.

Note that, I find it very strange when you say you want to use simulated annealing for discrete optimization problem like the one you mention. When your problem is discreet, how do you do differential? Thus, how do you know which direction you should proceed with gradient ascent/descent?

There are cases in which a seemingly discreet optimization problem is actually a continuous one in which you can use a customized and modified gradient ascent/descent with an optional simulated annealing. I will refrain from comment further in this particular case.