Algorithm to share/settle expenses among a group

Question

Hi All -

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

You have described it already. Sum all the expenses (1500 in your case), divide by number of people sharing the expense (500). For each individual, deduct the contributions that person made from the individual share (for person A, deduct 400 from 500). The result is the net that person "owes" to the central pool. If the number is negative for any person, the central pool "owes" the person.

Because you have already described the solution, I don't know what you are asking. Maybe you are trying to resolve the problem without the central pool, the "bank"?

I also don't know what you mean by "start with the least spent amount and work forward."

Answer 2

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

Answer 3

Straightforward, as you do in your text:

Returns expenses to be payed by everybody in the original array. Negativ values: this person gets some back

Just hand whatever you owe to the next in line and then drop out. If you get some, just wait for the second round. When done, reverse the whole thing. After these two round everybody has payed the same amount.

procedure SettleDepth(Expenses: array of double);
var
  i: Integer;
  s: double;
begin
  //Sum all amounts and divide by number of people
  // O(n) 
  s := 0.0;
  for i := Low(Expenses) to High(Expenses) do
     s := s + Expenses[i];

  s := s / (High(Expenses) - Low(Expenses));

  // Inplace Change to owed amount
  // and hand on what you owe
  // drop out if your even 
  for i := High(Expenses) downto Low(Expenses)+1 do begin
     Expenses[i] := s - Expenses[i];
     if (Expenses[i] > 0) then begin
        Expenses[i-1] := Expenses[i-1] + Expenses[i];
        Expenses.Delete(i);
     end else if (Expenses[i] = 0) then begin
        Expenses.Delete(i);
     end;
  end;

  Expenses[Low(Expenses)] := s - Expenses[Low(Expenses)];
  if (Expenses[Low(Expenses)] = 0) then begin
     Expenses.Delete(Low(Expenses));
  end;

  // hand on what you owe
  for i := Low(Expenses) to High(Expenses)-1 do begin
     if (Expenses[i] > 0) then begin
        Expenses[i+1] := Expenses[i+1] + Expenses[i];
     end;
  end;
end;

Answer 4

very pseudocode

SortFromLeastToMostSpent;
expense = CalculateExpense;

I := 0;
J := Count;

while I < J do
begin
  transfer = Min(expense - Spent(I), Spent(J) - expense);
  Inc(Spent[I], transfer);
  Dec(Spent[J], transfer);

  WriteToLog('Transfered <transfer> from <I> to <J>);

  if Spent[I] = expense then Inc(I);
  if Spent[J] = expense then Inc(J);
end;

Answer 5

Hi guys. To have worked on that, I know this is not at all an easy job :) So good luck... You can use http://www.tricount.com. It works fine !