我需要核对银行交易。匹配是当一组交易的总和为零时。匹配越小，匹配的等级越高。 这是子集求和问题 (NP Complete) 的变体。 然而: 没有那么多交易(通常最多10K) 总和限制为 10M，因此在这些条件下可能有一个实用的解决方案。 最大组大小可以限制为 10 个事务。
感谢所有提供帮助的人。
最佳答案
您可以使用 sudomakeinstall2 提到的动态规划。您需要为每个金额存储用于获得它的金额(因此您可以回溯到交易，以构建实际的组，而不仅仅是回答真/假)。
如果一个总和有太多路径(获得这个总和的可能性太多)，那么它就毫无意义(太多的可能性无法协调)，您可能会忽略长路径。
在计算总和时，对具有相似引用/日期/详细信息的交易使用过滤器。
您可能想要进行几次迭代。首先尝试只查找小的组。这应该很快，然后您可以在寻找更大的组之前删除该组中的所有事务。
希望这对您有所帮助。
关于algorithm - 特定情况下的子集和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39684133/