mob picking - random selection of multiple items, each with a cost, given a range to spend

I am considering a random mode for a real-time strategy game.

In this mode, the computer opponent needs to generate a random group of attackers (the mob) which will come at the player. Each possible attacker has an associated creation cost, and each turn there is a certain maximum amount to spend. To avoid making it uninteresting, the opponent should always spend at least half of that amount.

The amount to spend is highly dynamic, while creation costs are dynamic but change slower.

I am seeking a routine of the form:

void randomchoice( int N, int * selections, int * costs, int minimum, int maximum )

Such that given:

N = 5 (for example, I expect it to be around 20 or so)
selections is an empty array of 5 positions
costs is the array {11, 13, 17, 19, 23}
minimum and maximum are 83 and 166 

Would return:

83 <= selection[0]*11 + selection[1]*13 + selection[2]*17 + select开发者_开发百科ion[3]*19 + selection[4]*23 <= 166

Most importantly, I want an uniformly random selection - all approaches I've tried result mostly in a few of the largest attackers, and "zergs" of the small ones are too rare.

While I would prefer solutions in the C/C++ family, any algorithmic hints would be welcome.

---

Firstly I suggest you create a random number r between your min and max number, and we'll try to approach that number in cost, to simplify this a bit., so min <= r <= max.

Next create a scheme that is uniform to your liking in dispatching your units. If I understand correctly, it would be something like this:

If a unit A has a cost c, then m_a = r / c is the rough number of such units you can maximally buy. Now we have units of other types - B, C, with their own costs, and own number m_b, m_c, etc. Let S = m_a + m_b + .... Generate a random number U between 0 and S. Find the smallest i, such that S = m_a + ... m_i is larger than U. Then create a unit of type i, and subtract the units cost from r. Repeat while r > 0.

It seems intuitively clear, that there should be a more efficient method without recomputations, but for a given meaning of the word uniform, this is passable.

---

Truly uniform? If the number of types of units (N=20?) and cost to max spend ratio is relatively small, the search space for valid possibilities is fairly small and you can probably just brute force this one. Java-esque, sorry (more natural for me, should be easy to port.

List<Integer> choose(int[] costs, int min, int max) {
   List<List<Integer>> choices = enumerate(costs, min, max);
   return choices.get(new Random().nextInt(choices.size()));
}

// Recursively computes the valid possibilities.
List<List<Integer>> enumerate(int[] costs, int min, int max) {
   List<List<Integer>> possibilities = new ArrayList<List<List<Integer>>();

    // Base case
    if (costs.length == 1) { 
       for (int i = min / costs[0]; i < max / costs[0]; i++) {
           List<Integer> p = new ArrayList<Integer>();
           p.add(i);
           possibilities.add(p); 
       }   
       return possibilities;
    }

    // Recursive case - iterate through all possible options for this unit, recursively find
    // all remaining solutions. 
    for (int i = 0; i < max / costs[0]; i++) {
        // Pythonism because I'm lazy - your recursive call should be a subarray of the
        // cost array from 1-end, since we handled the costs[0] case here.

        List<List<Integer>> partial = enumerate(costs[1:], min - (costs[0] * i), max - (costs[0] * i));
        for (List<Integer> li : partial) {
          possibilities.add(li.add(0, i));
        }
    }

    return possibilities;
}