如何在一个百分比数组中最优地分配值？

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;
}

然而，假设每个计数器都是一个对象, 因此必须是整体的。如果我想在一个不同的值上尽可能平均地分配它们，该怎么办呢？比如说这个值是12。

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

当我需要整数时，如何处理小数？ 四舍五入可能会导致我没有所需的12个部分。

一个正确的算法应该：

输入/遍历值数组（本例中使用上面定义的数组）。

将其转换为一组整数值，这些整数值加在一起等于该值（对于此示例，该值将等于100）。

输出一个值数组，例如[10,50,20,20]（它们加起来为100，这是我们需要将它们加起来并且都是整数）。

如果任何值不是整数，则应使其成为整数，以便整个数组仍然加起来等于所需值（100）。

简而言之，在将值分配到数组中并尝试将它们转换为整数时如何处理小数。

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

- Alexander Craggs

---

请问您能否提供输入和期望输出，以使其更加清晰明了？ - Amit Joki

@AmitJoki 当然，我现在会添加它。 - Alexander Craggs

“必须是整数”这句话的意思是它必须是（正）整数吗？如果你想保留数据的细节而不失精度，你要么不使用整数，要么使用一个不可能的大因子（但这并不能确保你覆盖所有情况：想想像π这样的无理数，你永远无法用一个公共除数将其转换为整数）。 - Terry

@Terry 是的，我需要这个程序用于现实生活中的对象，这些对象不能被分成两个（或更多）部分，也不能有负值。我不知道为什么我没有使用整数这个术语。 - Alexander Craggs

也许可以帮助你在谷歌上搜索：你正在尝试对连续变量分布进行量化。 - user2314737

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;

最后一行需要一些解释。在 for(..) 循环中，i 的值将比允许的最大整数多1，因此它将是：

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算法。

为了简化问题，我在这里将展示如何在一维中实现它（这就是你的情况）。

让我们先讨论一个术语：余数。这是在你四舍五入数字后剩下的东西。它被计算为你希望得到的值与实际值之间的差：

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 ]

只有当所有值都远离0时，您才能确信最后一个值也将为正。因此，对于一般情况下的Bresenham算法需要使用floor函数，从而得出以下实现：

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）。

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

- pid

---

哇，真的是太棒了！如果我可以给它更多的赞，我一定会的。你使用的方法非常有趣，我从未意识到这个问题会变得如此复杂。再次感谢你。 - Alexander Craggs

在 Bresenham 算法中，如果输入数组的最后一个值为0，如何解决？这会导致输出数组中出现一些大于1的值，这是不期望的。 - Muskan Khedia

这是因为它带有累积误差，所以它大于1。在0值之间也会发生这种情况，这是可以预料的。为了避免这种情况，请使用不同的舍入函数，但要注意其他的不便之处。否则，您可能想尝试Leos Literak提出的解决方案，它具有非常有效的误差补偿方法。 - pid

Answer 2

备用实现 - 它会记住最大舍入值的指针，当总和与100不同时，增加或减少该位置上的值。

const items = [1, 2, 3, 5];
const total = items.reduce((total, x) => total + x, 0);
let result = [], sum = 0, biggestRound = 0, roundPointer;

items.forEach((votes, index) => {
  let value = 100 * votes / total;
  let rounded = Math.round(value);
  let diff = value - rounded;
  if (diff > biggestRound) {
    biggestRound = diff;
    roundPointer = index;
  }
  sum += rounded;
  result.push(rounded);
});

if (sum === 99) {
  result[roundPointer] += 1;
} else if (sum === 101) {
  result[roundPointer] -= 1;
}

- Leos Literak