找出一组数字中的哪些组合加起来得出给定的总数

我的任务是帮助一些会计师解决他们遇到的一个常见问题-给定交易清单和总存款,哪些交易是存款的一部分?例如,说我有这个数字列表:

1.00

2.50

3.75

8.00

而且我知道我的总存款是10.50,我可以很容易地看出这是由8.002.50交易组成的。但是,考虑到一百笔交易和几百万笔存款,很快就会变得困难得多。

在测试蛮力解决方案(花费太长的时间才能付诸实践)时,我有两个问题:

  1. 在大约60个数字的列表中,似乎可以找到十二个或更多组合来构成任何合理的总数。 似乎给定了即使是中等大小的随机数集合,您也可以找到多个组合,这些组合加起来几乎等于您想要的总数。

  2. 我为该问题构建了一个蛮力解决方案,但显然是O(n!),并且很快就失去了控制。除了明显的捷径(排除大于总数的数字)之外,还有没有办法缩短计算时间的方法?

明细金额列表按最大到最小排序,然后以下过程递归运行:

  • 取得列表中的下一项,查看是否将其添加到运行总计中可以使您的总计与目标匹配。如果是这样,请将当前链作为匹配项。如果未达到目标,请将其添加到运行总计中,将其从明细金额列表中删除,然后再次调用此过程

这样,它可以快速排除较大的数字,从而将列表缩减为仅需要考虑的数字。但是,它仍然是n!而且更大的列表似乎从未完成,因此我对加快速度可能会遇到的任何捷径感兴趣-

我怀疑即使从列表中删减1个数字也可以将计算时间缩短一半。

谢谢你的帮助!

回答:

背包问题的这种特殊情况称为子集和。

以上是 找出一组数字中的哪些组合加起来得出给定的总数 的全部内容, 来源链接: utcz.com/qa/426375.html

回到顶部