暴徒挑选-随机选择多个项目，每个项目都有成本，给定花费范围

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

最重要的是，我想要一个统一的随机选择--我尝试过的所有方法都会导致一些最大的攻击者，而小攻击者中的"zergs“太少了。

虽然我更喜欢C/C++家族的解决方案，但任何算法提示都是受欢迎的。

Answer 1

首先，我建议你在最小值和最大值之间创建一个随机数，我们将尝试在成本上接近这个数字，以简化这一点，所以min <= r <= max。

接下来，根据您的喜好创建一个统一的方案来调度您的单位。如果我理解正确的话，应该是这样的：

如果一个单元A有一个成本c，那么m_a = r / c是你可以最大限度购买的这样的单元的大致数量。现在我们有了其他类型的单元- B，C，有自己的成本，以及自己的数字m_b，m_c等。让S = m_a + m_b + ...。生成一个介于0和S之间的随机数U。找到最小的i，使S = m_a + ... m_i大于U。然后创建一个类型为i的单位，并从r中减去单位成本。重复while r > 0。

直觉上看起来很清楚，应该有一种更有效的方法，而不需要重新计算，但对于单词uniform的给定含义，这是可以通过的。

Answer 2

真正的统一吗？如果单元类型的数量(N=20?)成本与最大花费比率相对较小，有效可能性的搜索空间相当小，您可能只需暴力破解这一点。Java风格，对不起(对我来说更自然的是，应该很容易移植。

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