算法公平分账的方法，之后 :)

Question

我正在尝试解决一个你们可能也遇到过的现实问题：

你和朋友们一起吃晚饭，大家都同意平摊账单。可是，当账单终于来了，你发现并不是每个人都有足够的现金（有些人真抠门）。

所以，有些人支付的比其他人多……然后你回到家，想要弄清楚“谁欠谁多少钱”。

我想用算法来公平地解决这个问题 :)

一开始看起来很简单，但我在四舍五入等问题上卡住了，感觉自己真是个失败者 ;)

有没有什么好的建议来解决这个问题？

编辑：这里有一些Python代码，显示了我的困惑

>>> amounts_paid = [100, 25, 30]
>>> total = sum(amounts_paid)
>>> correct_amount = total / float(len(amounts_paid))
>>> correct_amount
51.666666666666664
>>> diffs = [amnt-correct_amount for amnt in amounts_paid]
>>> diffs
[48.333333333333336, -26.666666666666664, -21.666666666666664]
>>> sum(diffs)
7.1054273576010019e-015

理论上，所有差额的总和应该是零，对吧？

在另一个例子中，这个方法是有效的 :)

>>> amounts_paid = [100, 50, 150]
>>> total = sum(amounts_paid)
>>> correct_amount = total / float(len(amounts_paid))
>>> correct_amount
100.0
>>> diffs = [amnt-correct_amount for amnt in amounts_paid]
>>> diffs
[0.0, -50.0, 50.0]
>>> sum(diffs)
0.0

Answer 1

我不是Python方面的专家，但我觉得这个问题很有意思 =) 这是我的解决方案。开发时间大约45分钟。我写的Perl代码很简洁……应该很容易转换成其他语言。

~/sandbox/$ ./bistro_math.pl 
Anna owes Bill 7.57
Anna owes Mike 2.16
John owes Mike 2.62

~/sandbox/$ cat bistro_math.pl 
#!/usr/bin/perl
use strict;
use warnings;

### Dataset.
###    Bill total:  50.00
###    Paid total:  50.00
my @people = (
  { name => 'Bill', bill =>  5.43, paid => 13.00 },
  { name => 'Suzy', bill => 12.00, paid => 12.00 },
  { name => 'John', bill => 10.62, paid =>  8.00 },
  { name => 'Mike', bill =>  9.22, paid => 14.00 },
  { name => 'Anna', bill => 12.73, paid =>  3.00 },
);

### Calculate how much each person owes (or is owed: -/+)
calculate_balances(\@people);

### Tally it all up =)  This algorithm is designed to have bigger lenders
### paid back by the fewest number of people possible (they have the least
### hassle, since they were the most generous!).
sub calculate_balances {
  my $people = shift;

  ### Use two pools    
  my @debtors;
  my @lenders;

  foreach my $person (@$people) {
    ### Ignore people who paid exactly what they owed.
    $person->{owes} = $person->{bill} - $person->{paid};

    push @debtors, $person if ($person->{owes} > 0);
    push @lenders, $person if ($person->{owes} < 0);
  }

  LENDERS: foreach my $lender (@lenders) {
    next if ($lender->{owes} >= 0);

    DEBTORS: foreach my $debtor (@debtors) {
      next if ($debtor->{owes} <= 0);

      my $payment = ($lender->{owes} + $debtor->{owes} < 0) 
        ? abs $debtor->{owes} 
        : abs $lender->{owes};

      $lender->{owes} += $payment;
      $debtor->{owes} -= $payment;

      $debtor->{pays} = [] if (not exists $debtor->{pays});
      print "$debtor->{name} owes $lender->{name} $payment\n";

      next LENDERS if ($lender->{owes} >= 0);
    }
  }
}

exit;
~/sandbox/$ 

Answer 2

http://www.billmonk.com/

还有其他的。这个问题其实已经被解决过很多次了。

---

“理论上，所有的差值加起来应该是零，对吧？”

没错。不过，因为你用了 float，所以当人数不是2的幂时，会出现表示上的问题。

绝对不要在财务计算中使用 float。

绝对不要

一定要在财务计算中使用 decimal。

一定要

Answer 3

这个方法的关键是把每个人当作一个独立的账户来处理。

你可以很容易地从原始账单中算出每个人“应该”支付多少。把这个金额设为每个人的负数。接下来，记录每个人“已经支付”的金额，把支付的金额加到他们的账户上。到这个时候，支付过多的人（借出者）会有正余额，而支付不足的人（借入者）会有负余额。

没有一个绝对正确的答案来说明哪个借入者欠哪个借出者的钱，除了明显的情况就是只有一个借出者。借入者支付的金额可以分给任何一个借出者。只需把金额加到借入者的总额上，并从收到付款的借出者那里减去相应的金额。

当所有账户的余额都变为零时，说明每个人都已经支付完毕。

编辑（针对评论的回应）：

我觉得我的问题在于金额并不总是能整除，所以想出一个优雅处理这个问题的算法总是让我反复碰壁。

在处理美元和分的时候，没有100%完美的方法来处理四舍五入。有些人会比其他人多支付一美分。唯一公平的办法是随机分配这额外的$0.01（如有需要）。这只会在计算“欠款”时进行一次，也就是在分账单的时候。把货币值存储为分而不是美元有时会有帮助，比如$12.34可以存储为1234。这样你就可以使用整数而不是浮点数。

为了分配额外的分，我会这样做：

total_cents = 100 * total;
base_amount = Floor(total_cents / num_people);
cents_short = total_cents - base_amount * num_people;
while (cents_short > 0)
{
    // add one cent to a random person
    cents_short--;
}

注意：分配这些额外的分“随机”的最简单方法是把第一个额外的分分配给第一个人，第二个分给第二个人，依此类推。只有在你总是以相同的顺序输入相同的人时，这才会成为问题。