如何计算任意数字集合的总和,以及这些数字的所有子集？

Question

说我有一组数字:

Group1 = 10, Group2 = 15, Group3 = 20, Group4 = 30

我想输出所有数字子集的总和

10 + 15 = 25
10 + 15 + 20 = 45
10 + 15 + 20 + 30 = 75
15 + 20 = 35
15 + 20 + 30 = 65
20 + 30 = 50
10 + 20 = 30
10 + 30 = 40
10 + 20 + 30 = 60
... (assumed the rest is typed out)

这些组中的每一个都有一个名称,所以我想在结果之前打印出计算中使用的名称:

Group1 + Group2 = 25

怎么做这样的事情？

编辑:编辑标签的JacobM,这不是家庭作业,在你开始编辑之前会很感激.我实际上是在一个客户站点试图平衡一组数字,结果是错误的.我的想法是确定哪组数字等于2组之间的差值,这将直接识别问题.

注意:这将是浮点值,而不是整数.

EDIT2:添加任意,以便我可以理解我不能只用一堆string.format来输出一次..我可以在那一点轻松使用excel.

Answer 1

我的想法是确定哪组数字等于2组之间的差值,这将直接识别问题.

问题" 给定整数s和一组整数,将集合和的任何非空子集做到s？ "被称为" 子集和问题 ".这是非常好的研究,它是NP完全.(有关相关问题,请参阅此链接.)

也就是说,它是在合理的时间内解决的最难的问题之一.人们普遍认为(尽管目前尚未证实),对于这个问题,不可能存在多项式时间算法.对于包含n个元素的集合,您可以做的最好就是O(2 ^ n).

(我注意到你的问题是浮点数,而不是整数.只要你正确处理计算总和与目标总和的比较来处理可能在总和中产生的任何舍入误差,这并不重要. )

对于少数元素 - 你说你在集合中只有15个左右 - 你最好的选择就是彻底尝试它们.这是你如何做到的.

诀窍是要意识到从0到2 ^ n的每个整数都有一个子集.如果你看一下二进制中的那些数字:

0000
0001
0010
0011
...

每一个对应一个子集.第一个没有成员.第二个只有第1组.第三个只有第2组.第四个有第1组和第2组.依此类推.

伪代码很简单:

for each integer i from 1 to 2^n
{
  sum = 0;
  for each integer b from 1 to n
  {
    if the bth bit of i is on then sum = sum + group(b)
  }
  if sum == target then print out i in binary and quit
}
quit with no solution

显然这是O(n 2 ^ n).如果你能找到一个总是比O(c ^ n)更好的算法,或者证明你找不到这样的算法,那么你将永远成名.

维基百科的文章有一个更好的算法快得多给出了一个答案大多数但不是所有的时间.我会首先使用朴素算法,因为它只需要几分钟的时间来编写代码; 如果速度慢得令人无法接受,那就选择速度更快,更复杂的算法.