1

有一个等式：1a + 2b + 3c + 4d ... + 9i = 9

约束：1 <= a + b + c + ... + i <= 10 4

其中a,b,..,i是非负整数，每个整数都有一个特定的范围。

例如：1 <= a <= 5、2 <= b <= 3等等。

我需要找出这些变量的不同值集的数量，或者简单地说，解决该方程的方法的数量。

有一种递归方法可以解决这个问题，但这很慢。在给定的约束下，我无法想出一种有效解决此问题的方法。

4

3 回答 3

2

如果你仔细想想，解决方案实际上是非常有限的。

由于所有数字都是非负数，因此您有：

1a + 2b + 3c + 4d ... + 9i = 9

这意味着：

0 <= a <= 9
0 <= b <= 4
0 <= c <= 3
0 <= d <= 2
0 <= e <= 1
0 <= f <= 1
0 <= g <= 1
0 <= h <= 1
0 <= i <= 1

也就是说，只有10*5*4*3*2*2*2*2*2 = 19200一些情况需要考虑。

您可以遍历这些案例并找出哪些满足您的其他约束，哪些满足

1a + 2b + 3c + 4d ... + 9i = 9

提示：首先给出从i到的值a。这样，例如，i或的高值会h立即减小较小数字的可能值范围。

确保在计算之前应用MSalters的方法。尽管在这种情况下没有必要，因为问题太简单了，但总的来说它有很大帮助。

于 2012-08-07T10:42:59.650 回答
1

您基本上想要替换范围受到限制的变量，所以 a' = a+1, 0 <= a' <= 4和b' = b+2, 0 <= b' <= 1。从零开始使数学更容易。它还允许您将等式重写为1a' + 2b' + ... + 9i = 4。由于所有术语都是非负的，这极大地限制了搜索空间。例如，这意味着eupi必须全部为 0。这将等式简化为`1a' + 2b' + 3c + 4d = 4。

于 2012-08-07T10:43:48.380 回答
1

另一种解决方案是解决1a + 2b + 3c + 4d ... + 9i = 1（微不足道的）并找到1a + 2b + 3c + 4d ... + 9i = N+1给定解决方案的所有解决方案1a + 2b + 3c + 4d ... + 9i = N。这基本上是a => a+1或a=>a-1, b=>b+1或b=>b-1, c=>c+1等。

这是很好的递归，但只需要 8 次迭代即可达到 N=9，并且在每次迭代中，您只是增加或减少 9 个变量。

于 2012-08-07T10:56:21.770 回答