разделение счета алгоритмически и честно, потом :)

Хитрость заключается в том, чтобы рассматривать каждого человека как отдельную учетную запись.

Вы можете легко определить (по оригинальному счету), сколько каждый человек должен заплатить. Установите это как отрицательную сумму для каждого человека. Затем запишите сумму, которую каждый человек заплатил, добавив уплаченную сумму на свой счет. На этом этапе у людей, которые переплатили (кредиторы), будет положительный баланс, а у людей, которым недоплатили (заемщики), будет отрицательный баланс.

Не существует однозначного правильного ответа на вопрос, какой заемщик должен деньги каждому кредитору, за исключением очевидного случая, когда есть только один кредитор. Суммы, уплаченные заемщиком, могут перейти к любому из кредиторов. Просто добавьте сумму к общей сумме заемщика и вычтите суммы из суммы кредиторов, получающих платеж.

Когда все счета достигают нуля, все заплатили.

Изменить (в ответ на комментарии):

Я думаю, что моя проблема заключается в том, что сумма не всегда делится поровну, поэтому создание алгоритма, который элегантно справляется с этой задачей, меня снова и снова сбивает с толку.

При работе с долларами и центами не существует 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--;
}

Примечание: самый простой способ назначить монеты "случайным образом" - это назначить первый дополнительный цент первому человеку, второй - второму и т. д. Это становится проблемой только в том случае, если вы всегда вводите одни и те же люди в таком же порядке.

http://www.billmonk.com/

Среди других. Проблема уже решена. Много раз.

«Теоретически сумма разностей должна быть равна нулю, верно?»

да. Однако, поскольку вы использовали float, у вас возникают проблемы с представлением, когда количество людей не является степенью двойки.

Никогда. Использовать. float Для. Финансы.

Никогда

Всегда. Использовать. decimal Для. Финансы.

Всегда

Я не любитель питонов, но нашел интересную проблему =) Вот мое решение. Время разработки ~ 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/$ 

Вы знаете, сколько задолжали все и кому не хватило. Возьмите тот общий дефицит, который был у всех, и разделите его на тех, кто заплатил больше, начиная от самой высокой переплате до самой низкой.

«Проблема», которую вы видите, связана с двоичным представлением чисел с плавающей запятой, как объяснено здесь . В любом случае 7.1054273576010019e-015 - крошечное, крошечное число, поэтому, если вы округлите результаты до ближайшего цента, как и следовало бы, у вас не возникнет никаких проблем.