算法分摊账单&公平，事后:)

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

诀窍是把每个人都当做一个单独的账户。

你可以很容易地(从原始账单)确定每个人应该付多少钱。将此值设置为每个人的负数。接下来，记录每个人已经支付的金额，将支付的金额添加到他们的帐户中。在这一点上，支付过多的人(贷款人)将有正余额，而支付不足的人(借款人)将有负余额。

没有一个正确的答案是借款人欠每个贷款人的钱，除非在只有一个贷款人的明显情况下。借款人支付的金额可以流向任何贷款人。只需将金额加到借款人的总额中，然后从收到付款的贷款人中减去金额。

当所有账户都为零时，每个人都已经付清了。

编辑(回复评论)：

我认为我的问题在于数量并不总是可整除的，所以想出一个优雅地处理这个问题的算法似乎又一次让我绊倒了。

在处理美元和美分时，没有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--;
}

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

Answer 2

http://www.billmonk.com/

还有其他的。问题已经解决了。很多次了。

“从理论上讲，差的和应该是零，对吧？”

是。但是，由于您已经使用了float，所以当人数不是2的幂时，您就会遇到表示问题。

绝不可能。使用。float用于。金融。

从不

一直都是。使用。decimal用于。金融。

Always

Answer 3

我不是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/$