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?