## Finding small amounts from a larger total

## Finding small amounts from a larger total

(OP)

A customer pays a cheque of x pounds.

The customer has y number of outstanding invoices.

The whole value of the cheque pays off some of the invoices completely.

The customer is an unhelpful swine and doesn't detail the payments.

Is there some test that can determine which invoices from y that the payment x covers ?

Does that make sense ?

The customer has y number of outstanding invoices.

The whole value of the cheque pays off some of the invoices completely.

The customer is an unhelpful swine and doesn't detail the payments.

Is there some test that can determine which invoices from y that the payment x covers ?

Does that make sense ?

My Feeblegirl.com Forum boards for mmorpgs, sport, fun, politics...

www.jediknightsforum.com

## RE: Finding small amounts from a larger total

-- Chris Hunt

Webmaster & TragedianExtra Connections Ltd

## RE: Finding small amounts from a larger total

<.

## RE: Finding small amounts from a larger total

Something like the following algorithm should work.

Store the invoices in an array called Inv. Sort Inv into ascending order of pounds.

x is the amount of the cheque in pounds.

Locate the highest value in Inv that is less than or equal to x, keep a note of it and subtract that value from x.

Repeat the above until either x is zero (in which case you have found a solution - there may be several solutions) or you have reached the smallest value in Inv and x is not zero (in which case you need to start again (resetting x to its starting value) but this time use the next highest value in Inv as your starting point.

I could code it in Pascal if you really need it.

Andrew

Hampshire, UK

## RE: Finding small amounts from a larger total

<.

## RE: Finding small amounts from a larger total

Andrew

Hampshire, UK

## RE: Finding small amounts from a larger total

I think you're right in implying that proper ordering could ameliorate an otherwise brute-force operation. Clearly any invoice that exceeds the amount of the cheque should be excluded, but I think the invoices should be considered in date order (oldest first) somehow - as they're more likely to be settling an old invoice than a new one.

-- Chris Hunt

Webmaster & TragedianExtra Connections Ltd

## RE: Finding small amounts from a larger total

Perhaps Guthro will indicate whether invoice date should be considered but this might resolve itself to simply paying off the oldest invoices in strict chronological order which is not very interesting ...

Andrew

Hampshire, UK

## RE: Finding small amounts from a larger total

1. Do you take the largest always first, or try for a best fit?

2. Smallest first to try to take out the largest # of invoices with the payment (this algorithm would take care of ChrisHunt's hypothetical situation)?

3. Brute force?

4. (another suggestion) test each of your invoices for divisability (is

payment amountmodinvoice amount= 0?) Actually this might be the ticket for the best way to handle this, test each one for divisability, if total invoice is even, always consider even numbers unless you use two odd numbers (which always add up to even).(I did a floppy disk fill program a long time ago which involves the same problem (

a best-fit algorithm), roughly. It's an interesting one.)## RE: Finding small amounts from a larger total

like Chris suggested it's a good assumtion the user has paid the oldest invoices. So a good start would be add up all invoices and subtract the newest one(s) to see if that matches.

Another reason why the paid amount does not fit would be a typo in the paid amount vs. sum of invoices.

Bye, Olaf.

## RE: Finding small amounts from a larger total

It's a mental thing to pay off as many invoices as you can, so you have the least amount of invoices left, regardless of the amounts of those invoices.

<.

## RE: Finding small amounts from a larger total

FAQ68-4742: Which of these numbers add up to my target number??

## RE: Finding small amounts from a larger total

Christiaan Baes

Belgium

"My old site" - Me

## RE: Finding small amounts from a larger total

although the solver works a treat if you just need one random combination that adds up, it might result in something very unlikely and possible combination can be so numerous that you can't get all.

(we've customers with over 1200 open invoices of which various with identical value)

I've tried once to create an algorhitm for this very issue.

I did manage to get something that would give me a series of likely results if there were any.

Points that can help to optimize are:

Credit notes are likely to be included. So one option is to add all the negatives to the paid amount.

Invoices that are disputed will not be included in the payment, so those can be taken out.

Customers are likely to pay the invoices according to due date.

So start with the oldest and then start adding the values of the consecutive invoices.

I don't have the actual code anymore, but if I remember correctly, I started at invoice 1, then incremented the range until it started exceeding the paid amount, read in all of the credit notes and tested if I could get to the amount by reducing the amount with those, until I got below again and then started incrementing again, etc. etc. I also built in 3 wildcards values that could be either taken out of the current range or added from outside of that range. Once I'd run out of options for the current series, I started decreasing the range from the bottom until I got below the amount again at which point the range started incrementing from the top again and so on.

Unfortunately, the number of permutations made it a rather lenghty process, i.e. 100 Invoices would take over 2.5 hours, but I did get a 75% hitrate and I wasn't that proficient in VBA at the time, so I'm sure that the code could have been tuned quite a bit.

Hope this helps you somewhat.

Cheers,

Roel

## RE: Finding small amounts from a larger total

Invoices are mostly paid oldest first yes, but the whole problem arises when the customer misses one and it tends to be one of the oldest. There's no way of knowing this until their payment is resolved to various invoices, which brings us back to the original problem.

Maybe if there are duplicate values to unpaid invoices, the oldest would be set as paid first, just to clear that from the total.

My Feeblegirl.com Forum boards for mmorpgs, sport, fun, politics...

www.jediknightsforum.com

## RE: Finding small amounts from a larger total

In the case I mention, they were in the building industry, and tradesmen (who were the client's customers) often paid whatever was 90 or 60 days overdue on their monthly statements! Or, they just paid 'something' towards their total liability.

Max Hugen

Australia

## RE: Finding small amounts from a larger total

From what I know, accountants work this by:

1) Sort the invoices ascending by the Due Date*.

2) Starting from the top, pay off as much as the payment allows.

3) On the final one if there isn't enough money to pay it in full, put the remaining money down as Amount Paid** against the invoice.

* Due Date gives the customer a time period to pay the invoice. It is usually 30 days but can be different depending on the t&c of that transaction. It is sorted by Due Date because for example:

Invoice 1 might be on 01/07 (US 07/01) and invoice 2 on 10/07 (US 07/10), but invoice 1 has a 30 day due date and invoice 2 has a 14 day due date. So invoice 2 is due first and should be paid first.

** The Amount paid field allows multiple payment to be made on an invoice. It gives you a balance if you subtract it from the Total.

## RE: Finding small amounts from a larger total

I am sure there are algorithms which give reasonable results, but I don't believe there is one which can truly do the job exhaustively, without some form of brute force involved.

In mathematics this type of problem is called "packing."

When I walk, I sometimes bump into things. I am closing my eyes so that the room will be empty.

## RE: Finding small amounts from a larger total

So sorting the outstanding invoices by their amount helps.

That can be done recursively and even if X is greater than all Yi amounts, you will not try every combination of Yi to match to X.

Bye, Olaf.