这是关于寻找其中元素具有约束的有序集合的多个组合的问题。
举个例子:
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
有人可以对解决此类问题的过程或伪代码给出一个总体思路吗?
非常感谢你!
最佳答案
一堆嵌套的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
始终为true,因此我们可以摆脱对max
的赋值中的b
调用。同样,(c+1) >= 20
始终为true,因此可以简化对d
的分配。您还可以看到
a + b + c + d
的最大可能值为540,而e
的最小可能值为95。该值大于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