algorithm - 将一个整数划分为 9 个有限制的非负整数

Question

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

约束条件:1 <= a + b + c + ... + i <= 10⁴

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

例如:1 <= a <= 5、2 <= b <= 3，依此类推。

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

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

Answer 1

如果您考虑一下，解决方案实际上非常有限。

由于所有数字都是非负数，并且您有:

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 ' 计算前的方法。尽管在这种情况下没有必要，因为问题太简单了，但总的来说它有很大帮助。