1

这是关于查找有序集合的多个组合的问题，其中元素具有约束。

举个例子：

a+b+c+d+e=635，可能是……

[0-90] + [1-120] + [50-150] + [20-200] + [30-250] = 635

一种解决方案使用多个求和，正如数学堆栈交换中所回答的那样。

https://math.stackexchange.com/questions/159197/combinatorics-using-constraints-and-ordered-set

有人可以大致了解解决此类问题的过程或伪代码吗？

非常感谢你！

4

2 回答 2

0

查看数学交换页面上发布的解决方案。每个 sigma 符号都是一个嵌套for循环。最里面的项 ,x给出为if。因此，您的算法应该是围绕 if 的四个嵌套循环。

于 2012-06-18T06:06:21.860 回答
0

一堆嵌套的 for 循环是最简单的方法。

伪代码：

let combinations = 0;
for a = 0 to 90
    for b = max(a+1, 1) to 120
        for c = max(b+1, 50) to 150
            for d = max(c+1, 20) to 200
                let e = 635 - a - b - c - d;
                if max(d+1, 50) <= e <= 250
                    let combinations = combinations + 1

更新

上面可以稍微优化一下，但你最终会得到一个特定的，而不是一般的解决方案。

您可以观察到这(a+1) >= 1始终是正确的，因此我们可以摆脱对 的max调用b。同样，(c+1) >= 20总是正确的，因此d可以简化分配给。

您还可以看到 的最大可能值为a + b + c + d540，这给出了 95 的最小可能值e。这大于规定的下限e，所以我们只需要检查一下e >= (d+1)。

我们最终得到：

let combinations = 0;
for a = 0 to 90
    for b = a+1 to 120
        for c = max(b+1, 50) to 150
            for d = c+1 to 200
                let e = 635 - a - b - c - d;
                if d+1 <= e <= 250
                    let combinations = combinations + 1
于 2012-06-18T06:20:47.627 回答