算法 – 找出一组中的数字组合加起来给定总数

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

1.00
2.50
3.75
8.00

而且我知道我的总存款是10.50,我可以很容易地看到它是由8.00和2.50交易组成的.然而,由于一百笔交易和数百万笔存款,迅速变得困难重重.

在测试一个强力解决方案(需要太长时间才能实践)的时候,我有两个问题:

>有一个约60个数字的列表,似乎找到十几个或更多的组合任何总数是合理的.我期待一个单一的组合来满足我的总体,或者可能的几个可能性,但总是似乎有大量的组合.是否有一个数学原理来描述为什么会这样?似乎给定了一个甚至中等大小的随机数的集合,您可以找到一个多个组合,这些组合可以添加到您想要的任何总数.
>我为这个问题建立了一个强力解决方案,但这显然是O(n!),并且迅速失去控制.除了明显的捷径(排除大于总数的数字)之外,是否有办法缩短计算时间?

关于我当前(超慢)解决方案的详细信息:

详细数量列表按照最小排序,然后以下过程递归运行:

>拿下列表中的下一个项目,看看是否将其添加到正在运行的总计中,使您的总体匹配目标.如果是,则将当前链条作为匹配项.如果不符合您的目标,请将其添加到运行总计中,将其从详细数量列表中删除,然后再次调用此过程

这样一来,它可以快速排除较大的数字,将列表减少到只需要考虑的数字.但是,它仍然是n!而更大的列表似乎没有完成,所以我有兴趣可以加快速度的任何快捷方式 – 我怀疑即使从列表中删除1个数字也可以将计算时间缩短一半.

谢谢你的帮助!

背包问题的这种特殊情况称为 Subset Sum.
相关文章
相关标签/搜索