выбор моба - случайный выбор нескольких предметов, каждый со стоимостью, с учетом диапазона расходов

Question

Я рассматриваю случайный режим для стратегии в реальном времени.

В этом режиме компьютерный противник должен генерировать случайную группу атакующих (моб), которая придет к игроку.Каждый возможный злоумышленник имеет связанную стоимость создания, и каждый ход имеет определенную максимальную сумму, которую можно потратить.Чтобы не сделать это неинтересным, оппонент должен всегда тратить как минимум половину этой суммы.

Сумма расходов очень динамична, а затраты на создание динамичны, но меняются медленнее.

Я ищу подпрограмму в форме:

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

Так, что дано:

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 

Вернется:

83 <= selection[0]*11 + selection[1]*13 + selection[2]*17 + selection[3]*19 + selection[4]*23 <= 166

Большинствоважно, чтобы я выбрал равномерно случайный отбор - все попытки, которые я пробовал, приводят в основном к нескольким из самых крупных атакующих, а «зерги» из мелких слишком редки.

Хотя я бы предпочел решения вC / C ++, любые алгоритмические подсказки приветствуются.

Answer 1

Действительно равномерно? Если количество типов единиц (N = 20?) И соотношение затрат к максимальным расходам относительно невелико, пространство для поиска допустимых возможностей довольно мало, и вы, вероятно, можете просто использовать этот метод грубо. Java-esque, извините (более естественно для меня, должно быть легко портировать.

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;
}

Answer 2

Во-первых, я предлагаю вам создать случайное число r между вашим минимальным и максимальным числом, и мы постараемся приблизиться к этому числу по стоимости, чтобы немного упростить это, поэтому min <= r <= max.

Затем создайте схему, которая будет единой по вашему вкусу при отправке ваших юнитов. Если я правильно понимаю, это было бы что-то вроде этого:

Если единица A имеет стоимость c, то m_a = r / c - это приблизительное количество таких единиц, которые вы можете максимально купить. Теперь у нас есть юниты других типов - B, C, со своими собственными затратами и собственным номером m_b, m_c и т. Д. Пусть S = m_a + m_b + .... Генерация случайного числа U между 0 и S. Найдите наименьшее значение i, такое, что S = m_a + ... m_i больше U. Затем создайте единицу типа i и вычтите стоимость единицы из r. Повторите, пока r > 0.

Кажется интуитивно понятным, что должен существовать более эффективный метод без перевычислений, но для данного значения слова равномерный это приемлемо.