5

如果我知道，变量 a、b、c、d、e 有多少种可能的组合：

a+b+c+d+e = 500

并且它们都是整数并且> = 0，所以我知道它们是有限的。

4

10 回答 10

11

@Torlack，@Jason Cohen：递归在这里是个坏主意，因为存在“重叠的子问题”。即，如果您选择aas1和bas 2，那么您还有 3 个变量加起来应该是 497；通过选择aas2和bas ，您会得到相同的子问题1。（这种巧合的数量随着数字的增长而爆炸式增长。）

解决此类问题的传统方法是动态规划：构建一个自下而上的子问题解决方案表（从“1 个变量的多少组合加起来为 0？”开始）然后通过迭代构建（ “ n 个变量的多少组合加起来为k ？”的解是“ n-1 个变量的多少组合加起来为j？”的解的总和，其中 0 <= j <= k）。

public static long getCombos( int n, int sum ) {
  // tab[i][j] is how many combinations of (i+1) vars add up to j
  long[][] tab = new long[n][sum+1];
  // # of combos of 1 var for any sum is 1
  for( int j=0; j < tab[0].length; ++j ) {
    tab[0][j] = 1;
  }
  for( int i=1; i < tab.length; ++i ) {
    for( int j=0; j < tab[i].length; ++j ) {
      // # combos of (i+1) vars adding up to j is the sum of the #
      // of combos of i vars adding up to k, for all 0 <= k <= j
      // (choosing i vars forces the choice of the (i+1)st).
      tab[i][j] = 0;
      for( int k=0; k <= j; ++k ) {
        tab[i][j] += tab[i-1][k];
      }
    }
  }
  return tab[n-1][sum];
}

$时间java组合
2656615626

实际0m0.151s
用户 0m0.120s
系统 0m0.012s
于 2008-09-12T20:04:30.877 回答
5

您的问题的答案是 2656615626。

这是生成答案的代码：

public static long getNumCombinations( int summands, int sum )
{
    if ( summands <= 1 )
        return 1;
    long combos = 0;
    for ( int a = 0 ; a <= sum ; a++ )
        combos += getNumCombinations( summands-1, sum-a );
    return combos;
}

在您的情况下，summands是 5 并且sum是 500。

请注意，此代码很慢。如果您需要速度，请缓存对的结果summand,sum。

我假设你想要数字>=0。如果需要>0，请将循环初始化替换为a = 1，将循环条件替换为a < sum。我还假设您想要排列（例如1+2+3+4+5加号2+1+3+4+5等）。如果需要，您可以更改 for 循环a >= b >= c >= d >= e。

于 2008-09-12T19:57:33.187 回答
2

几个月前，我为我父亲解决了这个问题……扩展供您使用。这些往往是一次性问题，所以我没有选择最可重复使用的......

a+b+c+d = 总和

i = 组合数

        for (a=0;a<=sum;a++)
        {
            for (b = 0; b <= (sum - a); b++)
            {
                for (c = 0; c <= (sum - a - b); c++)
                {
                    //d = sum - a - b - c;
                    i++
                }
            }
        }
于 2008-09-12T20:03:43.453 回答
2

这实际上是一个在面试中问的好问题，因为它很简单，你可以在白板上写下来，但又很复杂，如果他们考虑得不够仔细，可能会绊倒他们。此外，您还可以提供两个不同的答案，这会导致实现完全不同。

顺序很重要
如果顺序很重要，那么任何解决方案都需要允许任何变量出现零；因此，最直接的解决方案如下：

public class Combos {
    public static void main() {
        long counter = 0;

        for (int a = 0; a <= 500; a++) {
            for (int b = 0; b <= (500 - a); b++) {
                for (int c = 0; c <= (500 - a - b); c++) {
                    for (int d = 0; d <= (500 - a - b - c); d++) {
                        counter++;
                    }
                }
            }
        }
        System.out.println(counter);
    }
}

返回 2656615626。

顺序
无关紧要如果顺序无关紧要，那么解决方案并不难，因为您只需要确保零​​是不可能的，除非已经找到总和。

public class Combos {
    public static void main() {
        long counter = 0;

        for (int a = 1; a <= 500; a++) {
            for (int b = (a != 500) ? 1 : 0; b <= (500 - a); b++) {
                for (int c = (a + b != 500) ? 1 : 0; c <= (500 - a - b); c++) {
                    for (int d = (a + b + c != 500) ? 1 : 0; d <= (500 - a - b - c); d++) {
                        counter++;
                    }
                }
            }
        }
        System.out.println(counter);
    }
}

返回 2573155876。

于 2008-09-12T22:43:34.270 回答
1

一种看待问题的方法如下：

首先，a 可以是 0 到 500 之间的任何值。然后如果遵循 b+c+d+e = 500-a。这将问题减少了一个变量。递归直到完成。

例如，如果 a 为 500，则 b+c+d+e=0，这意味着对于 a = 500 的情况，b、c、d 和 e 的值只有一种组合。

如果a是300，那么b+c+d+e=200，其实和原来的问题是同一个问题，只是减少了一个变量。

注意：正如 Chris 所指出的，这是一种实际尝试解决问题的可怕方式。

链接文本

于 2008-09-12T19:14:19.017 回答
0

如果它们是实数，则无限......否则它有点棘手。

（好吧，对于实数的任何计算机表示都会有一个有限的计数......但它会很大！）

于 2008-09-12T18:54:01.547 回答
0

有通式，如果
a + b + c + d = N
则非负积分解的个数为C(N + number_of_variable - 1, N)

于 2012-11-11T17:14:37.240 回答
0

@Chris Conway 的答案是正确的。我已经使用适用于较小金额的简单代码进行了测试。

                    long counter = 0;
            int sum=25;

            for (int a = 0; a <= sum; a++) {
                for (int b = 0; b <= sum ; b++) {
                    for (int c = 0; c <= sum; c++) {
                        for (int d = 0; d <= sum; d++) {
                             for (int e = 0; e <= sum; e++) {
                           if ((a+b+c+d+e)==sum) counter=counter+1L;

                             }
                       }
                    }
                }
            }
            System.out.println("counter e "+counter);
于 2013-11-05T08:13:18.003 回答
0

数学答案是 504!/(500!* 4!)。

形式上，对于 x1+x2+...xk=n，非负数 x1,...xk 的组合数是二项式系数： (k-1)-combination out of a set of (n+k-1)元素。

直觉是从 (n+k-1) 个点中选择 (k-1) 个点，并使用两个所选点之间的点数来表示 x1,..xk 中的一个数字。

抱歉，我第一次回答 Stack Overflow 的数学版很差。

Just a test for code block

Just a test for code block

    Just a test for code block
于 2017-06-22T15:35:08.413 回答
-1

包括底片？无限的。

只包括正面？在这种情况下，它们不会被称为“整数”，而是“自然数”。在这种情况下......我无法真正解决这个问题，我希望我能，但我的数学太生疏了。可能有一些疯狂的整体方法来解决这个问题。我可以为周围的数学高手提供一些指导。

最终结果是 x，a 的范围是从 0 到 x，b 的范围是从 0 到 (x - a)，c 的范围是从 0 到 (x - a - b)，并且依此类推，直到 e。

答案是所有这些可能性的总和。

我正在尝试在 Google 上找到一些更直接的公式，但我今天的 Google-Fu 真的很低......

于 2008-09-12T19:19:45.743 回答