javascript - 我如何在一系列百分比上最佳地分配值？

Question

假设我有以下代码:

arr = [0.1,0.5,0.2,0.2]; //The percentages (or decimals) we want to distribute them over.
value = 100; //The amount of things we have to distribute
arr2 = [0,0,0,0] //Where we want how many of each value to go

要找出如何在数组中平均分配一百个很简单，这是一个例子:

0.1 * 100 = 10
0.5 * 100 = 50
...

或者使用 for 循环:

for (var i = 0; j < arr.length; i++) {
    arr2[i] = arr[i] * value;
}

但是，假设每个计数器都是一个对象，因此必须是完整的。我怎样才能平等地(尽可能多地)以不同的值(value)分配它们。假设值变为 12。

0.1 * 12 = 1.2
0.5 * 12 = 6
...

当我需要整数时如何处理小数？四舍五入意味着我可能没有所需的 12 件。

正确的算法会 -

通过值数组进行输入/迭代(对于此示例，我们将使用上面定义的数组。

将它变成一组整数值，加在一起等于值(为此等于 100)

输出一个值数组，在这个例子中它看起来像 [10,50,20,20](这些值加起来是 100，这是我们需要将它们加起来的值并且也是整数) .

如果任何值不完整，它应该使它完整，这样整个数组仍然加起来等于所需的值 (100)。

TL;DR 在数组上分配值并尝试将它们转换为整数时处理小数

注意 - 如果将其发布在不同的 stackoverflow 网站上，我需要的是编程，但实际问题可能会使用数学来解决。另外，我不知道如何表达这个问题，这使得谷歌搜索变得异常困难。如果我错过了一些非常明显的事情，请告诉我。

Answer 1

您应该在分配所有值时使用已知会均匀分布舍入的舍入对所有值进行舍入。最后，最后一个值将被分配不同的值以将总和四舍五入为 1。

让我们慢慢开始，否则事情会变得非常困惑。首先，让我们看看如何分配最后一个值以获得所需的总值。

// we will need this later on
sum = 0;

// assign all values but the last
for (i = 0; i < output.length - 1; i++)
{
    output[i] = input[i] * total;
    sum += output[i];
}

// last value must honor the total constraint
output[i] = total - sum;

最后一行需要一些解释。 i 将比 for(..) 循环中最后允许的 int 多一个，因此它将是:

output.length - 1 // last index

我们分配的值将使所有元素的 sum 等于 total。我们已经在赋值期间一次性计算了总和，因此不需要再次迭代元素来确定总和。

接下来，我们将解决舍入问题。让我们简化上面的代码，以便它使用一个我们将在稍后详细说明的函数:

sum = 0;
for (i = 0; i < output.length - 1; i++)
{
    output[i] = u(input[i], total);
    sum += output[i];
}

output[i] = total - sum;

如您所见，除了 u() 函数的引入外，没有任何变化。现在让我们专注于此。

u() 的实现有多种方法。

DEFINITION
u(c, total) ::= c * total

根据这个定义，您得到的结果与上面相同。它既精确又好，但正如您之前所问，您希望这些值是自然数(例如整数)。因此，虽然对于实数这已经是完美的，但对于自然数我们必须对其进行四舍五入。假设我们对整数使用简单的舍入规则:

[ 0.0, 0.5 [  => round down
[ 0.5, 1.0 [  => round up

这是通过以下方式实现的:

function u(c, total)
{
    return Math.round(c * total);
}

当您不走运时，您可能会向上舍入(或向下舍入)太多值，以至于最后一次值修正不足以满足总约束条件，而且通常，所有值似乎都偏离太多。这是一个众所周知的问题，存在一个在 2D 和 3D 空间中绘制线条的多维解决方案，称为 Bresenham algorithm .

为了让事情变得简单，我将在这里向您展示如何在一维中实现它(这是您的情况)。

让我们首先讨论一个术语:余数。这是你四舍五入后剩下的。它被计算为你想要的和你真正拥有的之间的差异:

DEFINITION
WISH ::= c * total
HAVE ::= Math.round(WISH)
REMAINDER ::= WISH - HAVE

现在想想。剩下的就像你从一张纸上剪下一个形状时丢弃的那张纸。剩下的那张纸还在那里，但你把它扔掉了。取而代之的是，只需将它添加到下一个切口，这样就不会浪费它:

WISH ::= c * total + REMAINDER_FROM_PREVIOUS_STEP
HAVE ::= Math.round(WISH)
REMAINDER ::= WISH - HAVE

这样您就可以保留错误并将其转移到计算中的下一个分区。这称为摊销错误。

这是 u() 的分摊实现:

// amortized is defined outside u because we need to have a side-effect across calls of u
function u(c, total)
{
    var real, natural;

    real = c * total + amortized;
    natural = Math.round(real);
    amortized = real - natural;

    return natural;
}

根据您的意愿，您可能希望有另一个舍入规则，如 Math.floor() 或 Math.ceil()。

我建议您使用 Math.floor()，因为它已被证明对于总约束是正确的。当您使用 Math.round() 时，您将获得更平滑 的摊销，但您可能会面临最后一个值不为正的风险。你可能会得到这样的结果:

[ 1, 0, 0, 1, 1, 0, -1 ]

只有当ALL VALUES 远离 0 时，您才可以确信最后一个值也将为正。因此，对于一般情况，Bresenham 算法 将使用 flooring，从而导致最后一个实现:

function u(c, total)
{
    var real, natural;

    real = c * total + amortized;
    natural = Math.floor(real); // just to be on the safe side
    amortized = real - natural;

    return natural;
}

sum = 0;
amortized = 0;
for (i = 0; i < output.length - 1; i++)
{
    output[i] = u(input[i], total);
    sum += output[i];
}

output[i] = total - sum;

显然，input 和 output 数组必须具有相同的大小并且 input 中的值必须是一个分区(总和为 1) .

这种算法在概率和统计计算中很常见。