我的任务是帮助一些会计师解决他们遇到的常见问题 - 给出交易清单和总存款,哪些交易是存款的一部分？例如,假设我有这个数字列表:
1.00
2.50
3.75
8.00
我知道,我的存款总额是10.50,我可以很容易地看到它弥补了中8.00和2.50交易.然而,鉴于一百笔交易和数百万美元的存款,它很快变得更加困难.
在测试蛮力解决方案(花费太长时间以实现)时,我有两个问题:
有了大约60个数字的列表,它似乎找到了十几个或更多的组合,任何合理的总数.我期待一个单一的组合来满足我的总数,或者可能是一些可能性,但似乎总是有很多组合.是否有一个数学原理描述了为什么会这样？看来,即使是中等大小的随机数集合,您也可以找到多个组合,几乎可以达到您想要的总数.
我为这个问题建立了一个强力解决方案,但它显然是O(n!),并且很快失控.除了明显的快捷方式(排除大于总数的快捷方式),有没有办法缩短计算时间？
我当前(超慢)解决方案的详细信息:
详细信息量列表从最大到最小排序,然后以下过程以递归方式运行:
通过这种方式,它可以快速排除较大的数字,将列表缩小到只需要考虑的数字.但是,它仍然是n!似乎永远不会完成更大的列表,所以我对我可以采取的任何快捷方式感兴趣 - 我怀疑即使从列表中删除1个数字也会将计算时间缩短一半.
谢谢你的帮助!