CODEWITHSUNDEEP
algorithm
user6876928
user6876928

Reputation:

Subset sum in a specific case

I need to reconcile bank transactions. A match is when the sum of a group of transactions is zero.The grade of the match is higher if the match is small. This is a variation of the subset sum problem (NP Complete). However: There are not so many transactions (usually up to 10K) The sum is limited to 10M so maybe, under these conditions there is a practical solution. The maximum group size can be limited to 10 transactions.

Thanks to anyone who helps.

Upvotes: 0

Views: 177

Answers (1)

O_Z
O_Z

Reputation: 1563

U can use dynamic programming as mentioned by sudomakeinstall2. You will need to store for each sum the sums used to get to it (so you can back trace to the transactions , to build the actual group, not just answer true/false).

If a sum has too many paths (too many possibilities to get this sum), than it's meaningless (too many possibilities to reconcile) and you might ignore long paths.

When calculating sums use filters for transactions with similar references/dates/details.

You might want to make a few iterations.First try to find only small groups.This should be fast, and then you can remove all the transaction in this groups before going for larger groups.

Hope this helps.

Upvotes: 1

Related Questions