如果我知道,变量 a、b、c、d、e 有多少种可能的组合:
a+b+c+d+e = 500
并且它们都是整数并且> = 0,所以我知道它们是有限的。
@Torlack,@Jason Cohen:递归在这里是个坏主意,因为存在“重叠的子问题”。即,如果您选择a
as1
和b
as 2
,那么您还有 3 个变量加起来应该是 497;通过选择a
as2
和b
as ,您会得到相同的子问题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
您的问题的答案是 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
。
几个月前,我为我父亲解决了这个问题……扩展供您使用。这些往往是一次性问题,所以我没有选择最可重复使用的......
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++
}
}
}
这实际上是一个在面试中问的好问题,因为它很简单,你可以在白板上写下来,但又很复杂,如果他们考虑得不够仔细,可能会绊倒他们。此外,您还可以提供两个不同的答案,这会导致实现完全不同。
顺序很重要
如果顺序很重要,那么任何解决方案都需要允许任何变量出现零;因此,最直接的解决方案如下:
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。
一种看待问题的方法如下:
首先,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 所指出的,这是一种实际尝试解决问题的可怕方式。
如果它们是实数,则无限......否则它有点棘手。
(好吧,对于实数的任何计算机表示都会有一个有限的计数......但它会很大!)
有通式,如果
a + b + c + d = N
则非负积分解的个数为C(N + number_of_variable - 1, N)
@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);
数学答案是 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
包括底片?无限的。
只包括正面?在这种情况下,它们不会被称为“整数”,而是“自然数”。在这种情况下......我无法真正解决这个问题,我希望我能,但我的数学太生疏了。可能有一些疯狂的整体方法来解决这个问题。我可以为周围的数学高手提供一些指导。
最终结果是 x,a 的范围是从 0 到 x,b 的范围是从 0 到 (x - a),c 的范围是从 0 到 (x - a - b),并且依此类推,直到 e。
答案是所有这些可能性的总和。
我正在尝试在 Google 上找到一些更直接的公式,但我今天的 Google-Fu 真的很低......