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

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, у вас возникают проблемы с представлением, когда число людей не является степенью двойки.Используйте.float Для.Финансы.

Никогда

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

Всегда

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

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

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

Answer 5

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