Algorithm for Matching Invoice Payments

For a better formatted document, download [login to view URL] Mathematical model / algorithm to assign a payment amount exactly to a number of outstanding invoice transactions. This is required for an accounts program that is being developed. Scenario: Customer pays x-amount as payment and there are y-number of outstanding invoices / credit notes. The objective is to second guess the customer and identify which invoices / credit notes the payment relates to. This may not always be possible because the customer records may not match ours. However, if the amount being paid is for some or all of the items in our list, then the algorithm should select the correct list of items. As the number of items in the list increase, the number of permutations grow exponentially. After predetermined number of attempts, the algorithm should either give up or make the best job it can (minimum outstanding balance; remaining balance can be zero or positive but NOT negative) before giving up. Amount Paid: x-amount Item Date Type Amount 1. 11/01/2011 Invoice Owed-amount1 2. 18/01/2011 Invoice Owed-amount2 3. 25/01/2011 Invoice Owed-amounr3 4. 03/02/2011 Invoice Owed-amount4 5. 08/02/2011 Credit Note Credit-amount1 6. 15/02/2011 Invoice Owed-amount5 7. 22/02/2011 Invoice Owed-amount6 8. 25/02/2011 Invoice Owed-amount7 9 28/02/2011 Invoice Owed-amount8 10. 04/03/2011 Credit Note Credit-amount2 11. 08/03/2011 Invoice Owed-amount9 Points to consider: The list of items will be in date order and the older items are likely (but not necessarily) to be paid before the newer ones. If there are any credit notes, then there is a big chance that it matches one or more invoices in the list. If credit notes cannot be matched to invoices, the credit balance may be added to the amount paid by the customer. It is possible that the amount paid is for the invoices only and the credit notes should be ignored. The algorithm should be efficient and take into account that the number of items will vary for each instance. Ideally I would like the solution in C# but will accept a flowchart or some other suitable form. I must have unrestricted rights to utilise the solution without infringing any copyright and without having to make any additional payments.