Find a subset of numbers equal to one number
The reason I am posting this post is because I am looking to reconcile customer receivables accounts where “payments” are sent to accounts rather than match open accounts and cleared. So here's my problem:
You have one number (payment), which must equal a subset of a given set of numbers (invoice amount). Simple example:
Pay $ 10,002
Invoices:
5001 2932 +876 98 21 9923 2069 123 432 765
I would like to pull out 5001, 2932 and 2069 from this set.
As a non-programmer, an Excel spreadsheet application is the easiest to create. Ideas?
You are talking about an NP-Complete issue called Subset-sum .
This basically means that it is generally very difficult to compute a subset of prices that adds up to your total. However, it is very easy to verify your answer as you are simply summing your answers together.
My guess is that if you want to study N prices, you will need to use about 2 ^ N cells in Excel to calculate this. The wikiepdia article linked above provides some heuristics for approximating this.
Bottom line - if you need to do it on a large scale (N, say in hundreds of thousands ), you have to rethink why you need to do it.
If you can find a way to do this very efficiently, prize may be involved .
source to share
I was working on a very similar Java application that matched receipts to receivables transactions. We have not tried to progamemically link summarized receipts to a single transaction or vice versa for a number of reasons. However, we allowed users to manually do this mapping. We only matched the receipt figures with the transaction figures, which matched if there were multiple repeat orders and transactions with the same amount, we matched only when there was the same amount of duplicate amounts.
source to share