In Splitting the Check, I describe how I determine receivables and payables after a trip where one person spends money on behalf of others. Once the totals are computed, determining who pays whom is a manual process. It doesn’t take long to optimize the transfers in your head for a small number of people. And when you’re done, even if it’s not optimal, it’s probably still OK.

I think the number of possible combinations is extremely large. You can start limiting it by, say, making sure everyone’s payments are rounded to the nearest dollar or that payments don’t push someone from owed to owes, or vice versa. But it’s still a difficult problem (for me).

When a problem is too hard, I just brute-force it. When brute-force is too hard or impossible, I just pick a way and see how it goes. For this problem, I picked the following algorithm: For each iteration, the person who owes the most pays the person who’s owed the most. I don’t know if that’s the best way, but it’s probably how I’d start if I were doing it manually. The only difference is that when it’s done manually, a better way can present itself during the process. Here’s the result with that algorithm:

BD is the only payee that has to cash more than one check and TO is the only payer that has to cut more than one check. Not too bad, I think. Then I did the reverse. The person owing the least starts paying the person who’s owed the least.

Identical? I didn’t expect that. OK, since the works done, I’ll do: the person who owes the least pays the person who owes the most

and the person who owes the most pays the person who owes the least.

I can’t get it down to less than four transactions, even manually, so that must be the minimum for this data set. Where these algorithms break down is when I have exactly offsetting amounts. If BC owed $260 and BP owes $260, I can eliminate one transaction. I should identify matches first, then apply any of the above algorithms. It won’t help this data set, but would be better on a data set that had an offsetting match.

Here’s the code for the first try:

Dim i As Long, j As Long

Dim clsPerson As CPerson

Dim clsPayee As CPerson

Dim dAmountPaid As Double

If clsPersons.Amount <> 0 Then Err.Raise 9999, , “Totals don’t equal zero”

‘Find the person who owes the most

Set clsPerson = clsPersons.MaxOwes

‘Do until everyone’s paid as much as possible

Do Until clsPerson Is Nothing

‘Find the person who’s owed the most

Set clsPayee = clsPersons.MaxOwed

If Not clsPayee Is Nothing Then

‘Pay the lesser of the two

dAmountPaid = clsPerson.Balance

If -clsPayee.Balance < dAmountPaid Then dAmountPaid = -clsPayee.Balance

clsPerson.AddPayee clsPayee, -dAmountPaid

clsPayee.AddPayee clsPerson, dAmountPaid

End If

‘Once paid, find the next highest

Set clsPerson = Nothing

Set clsPerson = clsPersons.MaxOwes

Loop

For i = 1 To clsPersons.Count

Set clsPerson = clsPersons.Item(i)

For j = 1 To clsPerson.Payees.Count

Set clsPayee = clsPerson.Payees.Item(j)

Debug.Print clsPerson.Initials & IIf(clsPayee.Amount > 0, ” gets from “, ” pays to “), _

clsPayee.Initials; ” the amount of “, Format(clsPayee.Amount, “$#,##0.00;($#,##0.00)”)

Next j

Next i

End Sub

You can download splitcheckpayment.xls.zip to see the other methods and the class modules.

Dick, logically, if we assume everyone is non-zero, then everyone needs to give or receive at least one transaction, so the absolute minimum number of transactions is MIN(p,n) where p=number of positive values and n=number of negative values. There will generally be at least one extra transaction because someone will have to pay two people because the amounts don’t cancel exactly. That matches your conclusions, ie a minimum of 4 payments unless there is a matching pair, when it only takes 3 transactions.

The approach most often used in restaurants, which is simplest if you are dealing with cash rather than cheques, is for all the debtors to pay one person, who then settles all the creditors. The number of transactions is one less than the number of people.

Hi Dick –

In another life, I used to play poker regularly, when the winners and losers were kept in a ledger book that was balanced (sum = zero) after each night. At the end of the run, the losers all paid into a common pot, and then winners were paid from the common pot. The supply officer did the necessary nagging. This is just like what dbb proposes. No one owed anyone a particular dollar.

As an aside, because of the salary differences of the many players, and that these were long-time working relationships, the maximum loss was pro-rated to $50 at the end, which also of course pro-rated the maximum winning. Everyone knew this, so the poker was not of the most serious type. ;-) I was usually a few bucks down. The CO was somehow always near $50 bucks up.

…mrt

dbb: Do you mean MAX(p,n)?Sounds like Michale’s other life was Navy (my other life too). I wonder if he was a bubble head?

From a non-code standpoint, it seems counter intuitive for Dick to have “the person who owes the most pays the person who’s owed the most”. At first glance it would seem that if you have a large full bucket (owes the most) one should try to fill as many small empty buckets as possible first to get them out of the way. Oh well, that’s what I get for thinking with the left side of my brain instead of the right.

You might be right Dan. After I did it, I thought that I should have went least/least. But then I thought both of those methods wipes out one person, so they’re probably a wash. By starting most/most, I’m leaving those smaller amounts to fill in the shrinking gaps – at least that’s my hindsight theory. I still don’t know if there’s a best first move.

Dan –

Yep. Guilty as charged… five boats…

…mrt

Michael –

Funny how we always seem to be able to “smell another one around”. I’ve done diesel boats, fast attacks, and boomers. Gave them 20 years and 20 minutes…. but that was 10 years ago (gasp! Am I THAT old already?).

Hi Dan –

2 fast ‘uns… 3 not so fast… Did 30 and sold back 60… and that was 10 years ago for me last summer… so you’re still a seapup ;-)

…mrt