Algorithm to share/settle expenses among a group

Question

I am looking forward for an algorithm for the below problem.

Problem: There will be a set of people who owe each other some money or none. Now, I need an algorithm (the best and neat) to settle expense among this group.

Person AmtSpent
------ ---------
A       400  
B      1000  
C       100  
Total  1500

Now, expense per person is 1500/3 = 500. Meaning B to give A 100. B to give C 400. I know, I can start with the least spent amount and work forward.

Can some one point me the best one if you have.

Thanks in advance.

To sum up, 1. Find the total expense, and expense per head.
2. Find the amount each owe or outstanding (-ve denote outstanding).
3. Start with the least +ve amount. Allocate it to the -ve amount.
4. Keep repeating step 3, until you run out of -ve amount.
s. Move to next bigger +ve number. Keep repeating 3 & 4 until there are +ve numbers.

Or is there any better way to do? I am just curious. :)

Answer 1

The best way to get back to zero state (minimum number of transactions) was covered in this question here.