查找等于单个数字的数字子集
我发表这篇文章的原因是，我希望协调客户应收账款账户，其中“付款”被过帐到账户，而不是与未结发票匹配并清算。所以这是我的问题：
有一个数字（付款）应该等于给定数字集（发票金额）的子集。简单示例：
付款 10,002 美元
发票金额：
5001 2932 第876章 98 21 9923 2069 123 第432章 765
我想要一种方法从这个集合中取出 5001、2932 和 2069。
作为一名非程序员，Excel 电子表格应用程序对我来说最容易创建。有想法吗？
The reason I place this post is that I am looking to reconcile customer accounts receivable accounts where "payments" are posted to accounts instead of matched with the open invoices and cleared. So here is my issue:
Have a single number (payment) that should equal a subset of a given set of numbers (invoice amounts). Simple example:
Payment $10,002
Invoices values:
5001
2932
876
98
21
9923
2069
123
432
765
I would want a way to pull out 5001, 2932 and 2069 from this set.
Being a non-programmer, an Excel spreadsheet application is easiest for me to create. Ideas?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您正在谈论一个名为 Subset-sum 的 NP 完全问题。
基本上，这意味着一般来说，计算总价格的子集在计算上非常困难。然而，检查您的答案非常容易，因为您只需将答案相加即可。
我的猜测是，如果您想检查 N 个价格，则必须在 Excel 中使用大约 2^N 个单元格来计算。上面链接的维基百科文章给出了一些近似这一点的启发式方法。
底线是，如果您需要大规模执行此操作（例如，N 为
数千数百），您应该重新思考为什么需要这样做。如果您能找到一种非常有效的方法，可能会获得奖品。
You're talking about an NP-Complete problem called Subset-sum.
Basically, this means that in general it is very computationally hard to compute the subset of prices that sums to your grand total. It is, however, very easy to check your answer since you merely sum your answers together.
My guess is, that if you want to examine N prices, you're going to have to use about 2^N cells in Excel to calculate this. The wikiepdia article linked above give some heuristics for approximating this.
Bottom line is, if you need to do this on a large scale (N is, say, in the
thousandshundreds) you should rethink why you need to do this.If you can find out a way to do it very efficiently, there may be a prize involved.
我开发了一个非常类似的 Java 应用程序，它将收据映射到应收账款交易。由于多种原因，我们没有尝试以编程方式将汇总收据链接到单个交易，反之亦然。但是，我们确实允许用户手动进行该映射。我们只是将收据数字映射到匹配的交易数字，如果存在多个相同金额的收据和交易，则仅当存在相同数量的重复金额时才进行匹配。
I worked on a very similar Java application that mapped receipts to accounts receivable transactions. We did not try to progammatically link summed receipts to a single transactions or vice-versa for a number of reasons. However, we did allow users to manually do that mapping. We just mapped receipt figures to transactions figures that matched, if there were multiple reciepts and transactions with the same amount, we only matched when there were the same number of duplicate amounts.