准确的单程便士计算

Question

我们有一个成本 C，必须分配给部门 1..n。另一种计算产生每个部门的份额，它是一个从0到1的数字，有超过5位小数。所有部门份额之和正好为1，但不一定相等。

目标是计算向每个部门计费的准确金额。账单金额必须与成本 C 完全匹配，不能少几分或多几分。此外，每个部门的份额不得要求零头。此外，虽然将剩余部分转储到最后一个部门是不公平的，但没有必要回顾以前的时间范围。请注意，简单地将每个部门的份额四舍五入到便士几乎总是会导致多/少几便士。

过于简单化的例子：C = 33.34 ，4 个部门各有 0.2500 份额。因为 33.34 * 0.25 = 8.335 所以你可以看到两个部门必须支付 8.33，两个部门必须支付 8.34。一项正确的分配是：d1=8.33，d2=8.34，d3=8.33，d4=8.34。如果四舍五入，每个部门将支付 8.34 美元，这会导致多出 0.02 美元。如果将其乘以更多的部门和更多的成本，最终会出现数百美元的差异。

我想在 1 遍中完成此操作，也就是说，我不想循环，发现我偏离了 0.02，然后再次循环并调整值，直到正确为止。我想一次性完成此操作。我还想知道这个算法是否有名字。

Answer 1

在Perl的：

#!/usr/bin/perl

use strict;
use warnings;

use Data::Dumper;

use List::AllUtils qw( sum );

print Dumper allocate(10_000, .23, .37, .4);
print Dumper allocate(33.34, .25, .25, .25, .25);
print Dumper allocate(100, 1/3, 1/3, 1/3);

sub allocate {
    my ($C, @shares) = @_;

    my @alloc;

    while ( my $share = shift @shares ) {
        push @alloc, sprintf '%.2f', $C * $share;
        $C -= $alloc[-1];
        my $denom = sum @shares;
        $_ /= $denom for @shares;
    }

    return \@alloc;
}

输出：

$VAR1 = [
          '2300.00',
          '3700.00',
          '4000.00'
        ];
$VAR1 = [
          '8.34',
          '8.33',
          '8.34',
          '8.33'
        ];
$VAR1 = [
          '33.33',
          '33.34',
          '33.33'
        ];

Answer 2

不要使用浮动。二者必选其一定点小数，或使用整数，这样你可以通过任何你缩放因子，就是以美元价值分割。

，永不曾经的使用浮点数计算钱。

Answer 3

我将其称为“运行总计”并按如下方式实现：

1. 计算 1 号部门所欠的份额（可能有舍入误差）
2. 让 1 号部门支付步骤 1 中计算出的金额
3. 计算部门 #1 和部门 #2 共同承担的份额
4. 让 1 部门支付步骤 3 中计算的金额，减去步骤 2 中实际支付的金额。
5. ETC。1、2 和 3 部门共同欠下的金额。

这将确保任何部门所经历的误差最多为一个舍入误差（而不是多个舍入误差之和），并且最终的总数是正确的。