一种算法，用于汇总所有组合的数字列表
一种算法，用于汇总所有组合的数字列表
提问于 2008-12-31 19:34:32
我有一个数字列表，我想把所有不同的组合加起来。例如：
- 编号为1,4,7和13
- 输出将为：
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有没有用不同的数字计算这个值的公式？
回答 13
Stack Overflow用户
发布于 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 = 25Stack Overflow用户
发布于 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
{ } = 0Stack Overflow用户
发布于 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的第四卷提供了生成位向量的所有可能值的算法。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/403865
复制相关文章
相似问题