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

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

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

接下来创建一个符合您派遣部队喜好的统一方案。如果我理解正确的话，它会是这样的：

如果一个单位 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 中减去单位成本。当 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;
}