set - 查找等于单个数字的数字子集

Question

我发布这篇文章的原因是我希望核对客户应收帐款帐户，其中“付款”已过帐到帐户，而不是与未结发票匹配并清算。所以这是我的问题：

有一个数字（付款），应该等于给定数字集（发票金额）的子集。简单的例子：

付款 $10,002

发票值：

5001 2932 876 98 21 9923 2069 123 432 765

我想要一种方法从这个集合中取出 5001、293​​2 和 2069。

作为非程序员，Excel 电子表格应用程序对我来说是最容易创建的。想法？

Answer 1

您正在谈论一个称为Subset-sum的 NP-Complete 问题。

基本上，这意味着通常在计算上很难计算总和的价格子集。然而，检查你的答案很容易，因为你只是把你的答案加在一起。

我的猜测是，如果你想检查 N 个价格，你将不得不在 Excel 中使用大约 2^N 个单元格来计算这个。上面链接的维基百科文章给出了一些近似此的启发式方法。

底线是，如果您需要大规模执行此操作（例如，N 是数千个），您应该重新考虑为什么需要这样做。

如果您能找到一种非常有效的方法，那么可能会有奖品。

Answer 2

我开发了一个非常相似的 Java 应用程序，该应用程序将收据映射到应收账款交易。由于多种原因，我们没有尝试以编程方式将汇总的收据链接到单个交易，反之亦然。但是，我们确实允许用户手动进行映射。我们只是将收据数字映射到匹配的交易数字，如果有多个收据和交易金额相同，我们仅在重复金额数量相同时进行匹配。