用N个数字相加得到和为S的方式数量

Question

用N个数字相加得到和为S的方式数量

algorithmsumdynamic-programming

17

假设 S = 5，N = 3，解决方案如下 - <0,0,5> <0,1,4> <0,2,3> <0,3,2> <5,0,0> <2,3,0> <3,2,0> <1,2,2> 等等。

一般情况下，可以使用 N 个嵌套循环来解决问题。运行 N 个嵌套循环，在其中检查循环变量是否总和为 S。

如果我们不知道 N，我们可以使用递归解决方案。在每个级别中，从 0 到 N 运行一个循环，然后再次调用函数本身。当我们达到 N 的深度时，看看得到的数字是否相加为 S。

还有其他动态编程解决方案吗？

- Hari Sundararajan

1

重复（在math.stackexchange上）：http://math.stackexchange.com/questions/2455/geometric-proof-of-the-formula-for-simplex-numbers - Alexandre C.

动态规划解决方案与经典的0-1背包问题并没有太大的区别。不同之处在于我们只关心完整的背包（对解决方案进行微小的更改），以及那些恰好包含N个物品的背包（对解决方案进行次要的更改）。 - moinudin

6个回答

6

有一个封闭形式的公式：二项式(s + n - 1, s)或二项式(s+n-1,n-1)

这些数字是单纯形数。

如果你想计算它们，可以使用对数伽玛函数或任意精度算术。

参见https://math.stackexchange.com/questions/2455/geometric-proof-of-the-formula-for-simplex-numbers

- Alexandre C.

我没有在那个链接中看到证明。二项式关系式 (s+n-1, s) 似乎符合预期。例如，当 s=5，n=2 时，我们有 binomial(5+2-1,2) --> binomial(6,2)=15，但我期望的是 6 (0,5; 1,4; 2,3; 3,2; 4,1; 5,0)，这是 binomial(n+s-1,s)，或者是 binomial(n+s-1,n-1)。也许我误解了，但我无法从您链接中的证明中验证。 - Josh Vander Hook

5

我有自己的公式。我和我的朋友Gio一起进行了调查报告。我们得到的公式是[2的(n-1)次方-1]，其中n是我们要查找其有多少个加数的数字。

让我们试试。

如果n为1：它的加数是o。没有两个或更多的数字可以相加得到1（不包括0）。让我们试试更高的数字。

让我们试试4。4的加数为：1 + 1 + 1 + 1、1 + 2 + 1、1 + 1 + 2、2 + 1 + 1、1 + 3、2 + 2、3 + 1。它们的总和是7。用公式检查。2的(4-1)次方-1=2的3次方-1=8-1=7。

让我们试试15。2的(15-1)次方-1=2的14次方-1=16384-1=16383。因此，有16383种方法可以将数字相加，使它们的和为15。

（注：加数仅为正数。）

（您可以尝试其他数字，以检查我们的公式是否正确。）

- Marvin Mercado

这很有帮助，但我认为问题是关于用x个数字加到4。因此，只有1、2、1是x = 3的解决方案。 - user3475234

3

这可以用以下方式计算：O（s + n） （如果您不介意使用近似值），则可以计算为O(1)。 假设我们有一个字符串，其中包含n-1个X和s个o。例如，对于您的示例，当时，一个示例字符串如下：

oXooXoo

请注意，X将o分成三个不同的组：长度为1、长度为2和长度为2。这对应于您的解决方案<1,2,2>。每个可能的字符串都给我们提供了一个不同的解决方案，通过计算一排o中的数量（0也是可能的：例如，XoooooX将对应于<0,5,0>）。因此，通过计算这种形式的可能字符串的数量，我们可以得到您问题的答案。

有s+(n-1)个位置可供选择s o，因此答案是Choose(s+n-1, s)。

- BlueRaja - Danny Pflughoeft

如果您没有所有范围[0..s]可供选择怎么办？如果您还有a和b，并且所有用于求和的数字都必须来自[a..b]，对于S = 5，N = 3，a = 1和b = 4，结果将是<1,1,3> <1,2,2> <1,3,1> <2,1,2> <2,2,1>和<3,1,1>，总共为6。是否有一个公式可以解决这个问题？ - Andrew Savinykh

1

有一个固定的公式可以求解答案。如果你想找到将N表示为R个元素之和的方式数，答案总是： (N+R-1)!/((R-1)!*(N)!) 或者换句话说： (N+R-1) C (R-1)

- user2107425

0

这实际上看起来很像汉诺塔问题，但没有只能在较大的盘子上叠放盘子的限制。您有S个盘子，可以以任何组合放置在N个塔上。这就是让我开始思考它的原因。

我怀疑我们可以推导出一个公式，而不需要递归编程。不过我还需要一点时间。

- nycdan

请查看我的答案以获取公式。 - Alexandre C.

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mark Byers · Accepted Answer

尝试使用这个递归函数：

f(s, n) = 1                                    if s = 0
        = 0                                    if s != 0 and n = 0
        = sum f(s - i, n - 1) over i in [0, s] otherwise

使用动态规划，您可以在评估f之后缓存其值，并在评估之前检查该值是否已存在于缓存中。