我有一个数字列表,我想把所有不同的组合加起来。例如:
1+4=5
1+7=8
1+13=14
4+7=11
4+13=17
7+13=20
1+4+7=12
1+4+13=18
1+7+13=21
4+7+13=24
1+4+7+13=25
有没有用不同的数字计算这个值的公式?
发布于 2008-12-31 19:40:34
要做到这一点,一种简单的方法是创建一个位集合,其中的位数与数字的位数一样多。在您的示例4中。
然后从0001到1111计数,并对集合上具有1的每个数字求和:
数字1,4,7,13:
0001 = 13=13
0010 = 7=7
0011 = 7+13 = 20
1111 = 1+4+7+13 = 25
发布于 2009-01-01 01:25:24
下面是一个简单的递归解决方案在Java语言中的样子:
public static void main(String[] args)
{
f(new int[] {1,4,7,13}, 0, 0, "{");
}
static void f(int[] numbers, int index, int sum, String output)
{
if (index == numbers.length)
{
System.out.println(output + " } = " + sum);
return;
}
// include numbers[index]
f(numbers, index + 1, sum + numbers[index], output + " " + numbers[index]);
// exclude numbers[index]
f(numbers, index + 1, sum, output);
}
输出:
{ 1 4 7 13 } = 25
{ 1 4 7 } = 12
{ 1 4 13 } = 18
{ 1 4 } = 5
{ 1 7 13 } = 21
{ 1 7 } = 8
{ 1 13 } = 14
{ 1 } = 1
{ 4 7 13 } = 24
{ 4 7 } = 11
{ 4 13 } = 17
{ 4 } = 4
{ 7 13 } = 20
{ 7 } = 7
{ 13 } = 13
{ } = 0
发布于 2008-12-31 19:49:41
最著名的算法需要指数时间。如果有一个多项式时间的算法,那么您将求解subset sum problem,从而求解P=NP problem。
这里的算法是创建长度等于一组数字的基数的位向量。修复一组数字的枚举(n_i)
。然后,枚举位向量的所有可能值。对于位向量的每个枚举(e_i)
,计算e_i * n_i
的和。
这里的直觉是,您通过位向量来表示数字集的子集,并生成该数字集的所有可能的子集。当位e_i
等于1时,n_i
在子集内,否则不在子集内。
Knuth的TAOCP的第四卷提供了生成位向量的所有可能值的算法。
https://stackoverflow.com/questions/403865
复制相似问题