通过算法分割账单&公平，之后:)

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

http://www.billmonk.com/

其中。问题已经解决了。很多次了。

---

“理论上，差异之和应该为零，对吧？”

是的。然而，由于您使用了 float，因此当人数不是 2 的幂时，您就会遇到表示问题。

绝不。使用。 浮动对于。金融。

从不

总是。使用。 十进制 对于。金融。

永远

Answer 2

诀窍是将每个人视为一个单独的帐户。

您可以（根据原始账单）轻松确定每个人应支付的金额。将此设置为每个人的负数。接下来，通过将支付到每个人的帐户的金额相加来记录每个人已支付的金额。此时，多付的人（贷方）将有正余额，而少付的人（借款人）将有负余额。

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

当所有账户都归零时，所有人都已付款。

编辑（回应评论）：

我认为我的问题在于这样一个事实：金额并不总是可以被整除，因此想出一种优雅地处理这个问题的算法似乎又让我陷入了困境。再次。

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

Answer 4

你知道每个人所欠的总额，以及谁欠缺的。把每个人的总空头金额从最高的多付者到最低的人分配给那些支付更多的人。

Answer 5

您看到的“问题”与浮点数的二进制表示有关，如此处。无论如何，7.1054273576010019e-015 是一个非常非常小的数字，因此，如果您将结果四舍五入到最接近的分（正如您应该做的那样），就不会有任何问题。