c# - 给定自定义范围，如何找到该范围内 n 个数字的所有组合，从而达到目标平均值？

Question

假设我想要从 83 到 86 的 10 个项目的所有组合，其平均值为 84。一些解决方案是:

+----+----+----+----+
| 83 | 84 | 85 | 86 |
+----+----+----+----+
|  0 | 10 |  0 |  0 |
|  1 |  8 |  1 |  0 |
|  2 |  6 |  2 |  0 |
|  3 |  4 |  3 |  0 |
+----+----+----+----+

是否有已知的算法可以找到我正在寻找的组合？特别是如果有一个用 C# 编写的，我将不胜感激。

Answer 1

这是一个平凡的线性组合。从每个值中减去 84；他们现在是 [-1, 0, 1, 2]。 0 是一个填充值——它不影响平均值。将计数命名为 a-d，我们有:

a, b, c, d >= 0
a = c + 2d
a + b + c + d = 10

这使得解决方案可以非常快速地用蛮力处理。遍历 c 和 d 的可能值；计算生成的 a 和 b 值，并打印。请注意，您的循环可能会受到其他限制的限制:

for d in [0 .. 3]
    for c in [0 .. (10 - 3*d) / 2]   // c can take only half the remaining count;
                                     // a gets the rest.
        a = c + 2*d
        b = 10 - (a + c + d)
        print (a, b, c, d)

输出:

0 10 0 0
1 8 1 0
2 6 2 0
3 4 3 0
4 2 4 0
2 7 0 1
3 5 1 1
4 3 2 1
5 1 3 1
4 4 0 2
5 2 1 2
6 1 0 3

这就是要点；实现细节留给读者作为练习。 :-)