可能的组合数量

Question

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

a+b+c+d+e = 500

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

Answer 1

@Torlack,@ Jason Cohen:递归在这里是一个坏主意,因为存在"重叠的子问题".也就是说,如果你选择aas 1和bas 2,那么你剩下的3个变量应该加起来为497; 你选择aas 2和bas 来到同一个子问题1.(随着数字的增长,这种巧合的数量会爆炸.)

攻击这种问题的传统方法是动态编程:从子问题的解决方案的自下而上构建一个表(从"1个变量的多少组合加0？"开始)然后通过迭代构建(溶液为"如何的许多组合ñ变量加起来ķ？"是溶液的总和为"的许多组合如何n-1个变量加起来Ĵ？" 0 <= Ĵ <= ķ).

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];
}

$ time java Combos
2656615626

real    0m0.151s
user    0m0.120s
sys 0m0.012s

Answer 2

你的问题的答案是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.