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

• Z时代
• 2024-01-10
• 分类：问答

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

1.00
2.50
3.75
8.00

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

在测试蛮力解决方案（花费太长的时间才能付诸实践）时，我有两个问题：

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

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

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

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

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

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

谢谢你的帮助！

回答：

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

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