找出一组数字中的哪些组合加起来得出给定的总数
我的任务是帮助一些会计师解决他们遇到的一个常见问题-给定交易清单和总存款,哪些交易是存款的一部分?例如,说我有这个数字列表:
1.002.50
3.75
8.00
而且我知道我的总存款是10.50
,我可以很容易地看出这是由8.00
和2.50
交易组成的。但是,考虑到一百笔交易和几百万笔存款,很快就会变得困难得多。
在测试蛮力解决方案(花费太长的时间才能付诸实践)时,我有两个问题:
在大约60个数字的列表中,似乎可以找到十二个或更多组合来构成任何合理的总数。 似乎给定了即使是中等大小的随机数集合,您也可以找到多个组合,这些组合加起来几乎等于您想要的总数。
我为该问题构建了一个蛮力解决方案,但显然是O(n!),并且很快就失去了控制。除了明显的捷径(排除大于总数的数字)之外,还有没有办法缩短计算时间的方法?
明细金额列表按最大到最小排序,然后以下过程递归运行:
- 取得列表中的下一项,查看是否将其添加到运行总计中可以使您的总计与目标匹配。如果是这样,请将当前链作为匹配项。如果未达到目标,请将其添加到运行总计中,将其从明细金额列表中删除,然后再次调用此过程
这样,它可以快速排除较大的数字,从而将列表缩减为仅需要考虑的数字。但是,它仍然是n!而且更大的列表似乎从未完成,因此我对加快速度可能会遇到的任何捷径感兴趣-
我怀疑即使从列表中删减1个数字也可以将计算时间缩短一半。
谢谢你的帮助!
回答:
背包问题的这种特殊情况称为子集和。
以上是 找出一组数字中的哪些组合加起来得出给定的总数 的全部内容, 来源链接: utcz.com/qa/426375.html