# 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?

• Simulated annealing does not seem to offer you any good advice at all. You should look at another similar concept Monte Carlo which is applicable. – InformedA Sep 15 '14 at 6:38
• @ginsunuva I edited your question to make it more clear as I understand it. Please verify, that this is indeed what you want to ask. – FrankW Sep 17 '14 at 10:07
• As long as their is no structure in the relationship between item, type and expense (you don't say anything about that!) there may be no better approach than enumerating all solutions (for an exact solution) or a random search (which may find a "good" solution faster). – Raphael Sep 17 '14 at 10:18
• Does the expense of assigning type A to variable 1 depend on the types assigned to the other variables? – FrankW Sep 17 '14 at 10:22
• It could. These are all variables in a program with different precisions. If one variable interacts with another, it probably would. Adding precision A to precision B would be the same as both being B. But we don't know how each variable interacts with one another (it'd be great if we did.) – ginsunuva Sep 17 '14 at 10:50