我的任务是帮助一些会计师解决他们遇到的一个常见问题 - 给出交易清单和总存款，哪些交易是存款的一部分？例如，假设我有这个数字列表：
1.00
2.50
3.75
8.00
我知道我的总存款是10.50，我可以很容易地看出它是由8.00 and 2.50交易。然而，考虑到一百笔交易和数百万笔存款，它很快就会变得更加困难。
在测试暴力解决方案时（这需要太长的时间才能实现），我有两个问题：
通过大约 60 个数字的列表，似乎可以找到十几个或更多的组合来获得合理的总数。我期待一个单一的组合来满足我的总体需求，或者可能有几种可能性，但似乎总是有很多组合。有没有数学原理可以描述这是为什么？似乎给定一个中等大小的随机数集合，您可以找到加起来几乎达到您想要的任何总数的多重组合。
我为这个问题建立了一个强力解决方案，但它显然是 O(n!)，并且很快就会失去控制。除了明显的捷径（排除大于总数本身的数字）之外，还有其他方法可以缩短计算时间吗？
我当前（超慢）解决方案的详细信息：
将详细金额列表从大到小排序，然后递归运行以下过程：
- 取出列表中的下一项，看看将其添加到您的运行总计中是否会使您的总计与目标相符。如果是，则将当前链保留为匹配项。如果未达到目标，请将其添加到运行总计中，将其从详细金额列表中删除，然后再次调用此流程
通过这种方式，它可以快速排除较大的数字，将列表缩减为仅需要考虑的数字。然而，还是n！更大的列表似乎永远不会完成，所以我对任何可以加快速度的捷径感兴趣 - 我怀疑即使从列表中删除 1 个数字也会将计算时间减少一半。
感谢您的帮助！
背包问题的这种特殊情况称为子集和 http://en.wikipedia.org/wiki/Subset_sum.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
