Since I assume the client can make partial payments, you won't always have an exact solution. I suggest you simply apply payments to the oldest invoices first - and perhaps leave the option open for a manual override (i.e., manually select individual invoices) - but doing anything different than the chronological order should be the exception, not the rule.

>In developing a form for a client that will accept payments and allow the user to apply a payment across multiple invoices, I wanted to have it be as smart as possible (while still being flexible) and apply the payment to the proper invoice or invoices. Some situations are simple. A payment that covers a single invoice is the simplest (they start off entering the invoice number, which allows me to retrieve all open invoices for that customer, and then I can select that invoice to be paid). If the payment covers two invoices, I can pay the first one and search for another with a balance equal to the unapplied portion of the payment. More than two gets dicey. I've actually come up with an algorithm that works quite reliably to figure out which invoices are being paid even if a payment covers between 3 and 9 invoices. But it's a tad kludgey and can take gobs of time in some situations (though in my testing, the most likely scenarios are handled quickly). I limit it to 2 seconds and
> then abandon it if it has not determined which invoices to pay by then. Again, it's really quite reliable.
>
>But I'm wondering about something a little better and more elegant. In my thoughts on this, I realized that putting the invoice balances in a matrix lets you quickly determine all combinations of two invoices:
>
>

>          458.25   154.99   1203.15   742.69
>458.25     1,1       1,2      1,3       1,4
>154.99     2,1       2,2      2,3       2,4
>1203.15    3,1       3,2      3,3       3,4
>742.69     4,1       4,2      4,3       4,4
>

>
>(NOTE: Although I used the PRE tag, it is not respecting my formatting. To view the matrix propery, slide the top row over so that 458.25 is over 1,1.)
>
>Draw a line from 1,1 to 4,4. That line represents a payment covering one invoice (already trivial). Everything above the line is combinations of two invoices (but a payment covering two invoices is also trivial). Everything below the line is meaningless. Extrapolating this out to a payment covering 3, 4, or more invoices was harder and I did not end up with a solution based on this.
>
>Does anyone know of a nice algorithm for this?
>
>Russell Campbell