如何将浮点数四舍五入为整数，同时保持它们的总和？

Question

假设我有一个由浮点数组成的数组，按升序排列，它们的总和已知为整数 N。我想要将这些数字“四舍五入”为整数，同时保持它们的总和不变。换句话说，我正在寻找一种算法，将浮点数数组（称为fn）转换为整数数组（称为in），使得：

1. 两个数组具有相同的长度
2. 整数数组的总和为N
3. 每个浮点数fn[i]与其对应的整数in[i]之间的差小于1（如果你真的必须，则等于1）
4. 假设浮点数是按排序顺序排列的（fn[i] <= fn[i+1]），整数也将按排序顺序排列（in[i] <= in[i+1]）

给定满足这四个条件的情况下，最小化四舍五入方差的算法（sum((in[i] - fn[i])^2)）是可取的，但这并不重要。

示例：

[0.02, 0.03, 0.05, 0.06, 0.07, 0.08, 0.09, 0.1, 0.11, 0.12, 0.13, 0.14]
    => [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[0.1, 0.3, 0.4, 0.4, 0.8]
    => [0, 0, 0, 1, 1]
[0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1]

=> [0, 0, 1, 1, 9, 9] 更加可取。 => [0, 0, 0, 0, 10, 10] 可接受。 [0.5, 0.5, 11] => [0, 1, 11] 可以。 => [0, 0, 12] 在技术上不被允许，但在紧急情况下可以使用。

回答一些评论中提出的好问题：

• 在两个数组中都允许有重复的元素（尽管我也想听听仅当浮点数数组不包含重复元素时才起作用的算法）。
• 没有单一正确的答案 - 对于给定的浮点数组，通常有多个整数数组满足这四个条件。
• 我所考虑的应用场景是 - 这有点奇怪 - 在MarioKart游戏中向获胜者分配积分；-)我自己从未玩过这个游戏，但是在看别人玩时，我注意到前4名之间分配了24个积分，并且我想知道如何根据完成时间分配积分（因此，如果某人领先很大，他们将获得更大的积分份额）。 游戏将整数跟踪为总积分，因此需要这种舍入。

---

对于好奇的人，这里是我用来确定哪些算法可行的测试脚本。

- David Z

---

如果你有一个包含1000个.001的数组会发生什么？你希望它如何表现？重复允许吗？ - ojblass

@ojblass：在这种情况下，您将把999个数字都舍入为0，然后将最后一个数字舍入为1。这就满足了要求。 - Jason Coco

我曾经在一些应用程序（如估算软件）中看到过这种需要，其中所有的金额都会四舍五入成美元，并且底线数字必须匹配。 - ojblass

还有一个相关的问题：https://dev59.com/wmYr5IYBdhLWcg3wq8CI - CMCDragonkai

相关：保留总和的批量舍入。 - burnabyRails

Answer 1

你可以尝试的一种选项是“级联舍入”。

对于该算法，您需要跟踪两个运行总数：浮点数和整数。 要获取下一个整数，您需要将下一个浮点数添加到您的运行总数中，四舍五入运行总数，然后从四舍五入后的运行总数减去整数运行总数：

number  running total   integer integer running total
   1.3       1.3          1           1
   1.7       3.0          2           3
   1.9       4.9          2           5
   2.2       8.1          3           8
   2.8      10.9          3          11
   3.1      14.0          3          14

- James Anderson

---

@mikko：[0.4, 0.2, 0.4, 0.4, 0.2, 0.4, ...] 真的已经排序了吗？ - artificialidiot

好的，我混淆了两个反例。原始的是[0.3, 0.3, 0.3, 0.3, ...]，它将变成类似于[0, 1, 0, 0, ...]的东西。[0.4, 0.2, 0.4, 0.2, ..]的例子应该是[0.4, 1.2, 2.4]，这证明了不太理想的舍入误差。因为第一个0.4四舍五入为0（误差0.4），1.2四舍五入为2（误差总和1.2），而2.4再次四舍五入为2（误差总和2.8），而最优解将会将0.4或2.4向上舍入（误差0.6），剩余的0.4向下舍入（误差总和1.0），1.2向下舍入（误差总和1.2）。 - Mikko Rantanen

Mikko：关于排序规则的观点很好。同时要注意，当有许多接近0和1的值时，这看起来非常奇怪。 - James Anderson

我一直在测试解决方案，看起来如果放弃排序要求，这个方案是可行的，尽管仍然不是最优的。 - David Z

以下是该算法的javascript实现的代码链接：https://jsfiddle.net/cd8xqy6e/ - Jake

Answer 2

以下是一种算法，应该能够完成任务。与其他算法的主要区别在于它总是按正确的顺序对数字进行四舍五入。 最小化舍入误差。

这种语言是一些伪代码，可能源自JavaScript或Lua。应该解释一下这一点。请注意基于1的索引（对于x到y循环更加友好。: p）

// Temp array with same length as fn.
tempArr = Array(fn.length)

// Calculate the expected sum.
arraySum = sum(fn)

lowerSum = 0
-- Populate temp array.
for i = 1 to fn.lengthf
    tempArr[i] = { result: floor(fn[i]),              // Lower bound
                   difference: fn[i] - floor(fn[i]),  // Roundoff error
                   index: i }                         // Original index

    // Calculate the lower sum
    lowerSum = lowerSum + tempArr[i].result
end for

// Sort the temp array on the roundoff error
sort(tempArr, "difference")

// Now arraySum - lowerSum gives us the difference between sums of these
// arrays. tempArr is ordered in such a way that the numbers closest to the
// next one are at the top.
difference = arraySum - lowerSum

// Add 1 to those most likely to round up to the next number so that
// the difference is nullified.
for i = (tempArr.length - difference + 1) to tempArr.length
    tempArr.result = tempArr.result + 1
end for

// Optionally sort the array based on the original index.
array(sort, "index")

- Mikko Rantanen

---

我刚刚回来测试这些，根据我目前所看到的情况，这似乎是为数不多的几个能够正常工作的！ - David Z

进一步阅读：https://en.wikipedia.org/wiki/Largest_remainder_method - Kostas Filios

Answer 3

一个非常简单的方法是将所有小数部分相加。根据您问题的定义，该数字必须是一个整数。从最大的数字开始平均分配这个整数，然后给第二大的数字一个...等等，直到您没有东西可以分配为止。

注意 这是伪代码...索引可能会有偏差...很晚了，我困了。

float accumulator = 0;

for (i = 0; i < num_elements; i++)  /* assumes 0 based array */
{
   accumulator += (fn[i] - floor(fn[i])); 
   fn[i] =  (fn[i] - floor(fn[i]);
}

i = num_elements;

while ((accumulator > 0) && (i>=0))
{
    fn[i-1] += 1;   /* assumes 0 based array */
    accumulator -= 1;
    i--;
}

更新: 还有其他的分配累计值的方法，基于对每个值进行了多少截断。这将需要保留一个名为loss[i] = fn[i] - floor(fn[i]) 的单独列表。然后，您可以重复使用fn[i]列表，并重复地给最大损失项1(然后将loss[i]设置为0) 。虽然有些复杂，但我想它可以工作。

- ojblass

---

嗯，我认为从大到小排序可以保持排序顺序的定义……我有什么遗漏吗？例如？ - ojblass

如果你从最大的、第二大的等开始——那么它们怎么会变得未排序呢？ - Marc Gravell

好答案 - 我喜欢这个 ;-p - Marc Gravell

那么[0.4，0.4，0.4，0.4，9.2，9.2]呢？我相信算法应该在这里提供一个[0, 0, 1, 1, 9, 9]的答案。 - Mikko Rantanen

我认为我的算法会得出 [0, 0, 0, 0, 10, 10]。 - ojblass

Answer 4

如何呢：

a) start: array is [0.1, 0.2, 0.4, 0.5, 0.8], N=3, presuming it's sorted
b) round them all the usual way: array is [0 0 0 1 1]
c) get the sum of the new array and subtract it from N to get the remainder.
d) while remainder>0, iterate through elements, going from the last one
   - check if the new value would break rule 3.
   - if not, add 1
e) in case that remainder<0, iterate from first one to the last one
   - check if the new value would break rule 3.
   - if not, subtract 1

- vgru

---

可以通过确定前n个值（其中n是浮点数和整数之和的差）来避免对数组进行排序。使用堆可以将获取前n个值的操作变为O(n)的复杂度。 - Georg Schölly

Answer 5

基本上，您要做的就是将舍入后的剩余部分分配给最有可能的候选者。

1.像平常一样对浮点数进行四舍五入，但跟踪从四舍五入中得出的差值以及与fn和in相关的索引。 2.按差值对第二个数组进行排序。 3.当sum（in） N时，从最大的正差开始向后工作，递减舍入值（确保仍满足规则＃3）。

示例：

[0.02, 0.03, 0.05, 0.06, 0.07, 0.08, 0.09, 0.1, 0.11, 0.12, 0.13, 0.14] N=1

1. [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] sum=0 and [[-0.02, 0], [-0.03, 1], [-0.05, 2], [-0.06, 3], [-0.07, 4], [-0.08, 5], [-0.09, 6], [-0.1, 7], [-0.11, 8], [-0.12, 9], [-0.13, 10], [-0.14, 11]]

2. 排序将反转数组

3.从最大的负余数开始工作，您会得到[-0.14, 11]。 递增`in[11]`，您会得到[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] sum=1 完成。

- lc.

---

顺便买个通量电容器。 - ojblass

是的，绝对同意这有点混乱，但应该能够工作。 - lc.

这应该可以工作。不过，你可以通过始终向一个方向（例如向下）四舍五入，然后从最大的 abs(delta) 开始进行补偿，使其更加清晰明了。 - Mikko Rantanen

按小数部分对数组进行排序将是额外的O(NlgN)步骤，但它将允许最小化最坏情况下的舍入误差。对于某些数据集，它仍可能无限接近于1（例如，如果有一百万个以.999999结尾的值，则必须向下舍入一个），但通过按delta排序，可以实现可用于任何给定数据集的最小绝对舍入误差。 - supercat

Answer 6

你能试试这样吗？

in [i] = fn [i] - int (fn [i]);
fn_res [i] = fn [i] - in [i];

fn_res → 是结果分数。(我觉得这是基础问题...), 我们有遗漏吗？

- Alphaneo

---

让我们用它的值替换 in [i]：fn_res [i] = fn [i] - ( fn [i] - int (fn [i]) ) = int (fn [i])。所以，似乎缺少了什么 ;) - ruvim

Answer 7

嗯，4是痛点。否则你可以做一些像“通常向下舍入并累加剩余部分；当累加器>=1时向上舍入”的事情。（编辑：实际上，只要交换它们的位置，这可能仍然可以）

也许有一种用线性规划来解决的方法？（那是数学“编程”，而不是计算机编程——你需要一些数学知识来找到可行的解决方案，尽管你可能可以跳过通常的“优化”部分）。

作为线性规划的一个例子——以[1.3、1.7、1.9、2.2、2.8、3.1]为例，你可以有以下规则：

1 <= i < 2
1 <= j < 2
1 <= k < 2
2 <= l < 3
3 <= m < 4
i <= j <= k <= l <= m
i + j + k + l + m = 13

然后应用一些线性/矩阵代数 ;-p 提示：有基于“Simplex”算法的产品来完成上述操作。这也是常见的大学课程内容（我在大学为我的毕业项目写了一个）。

- Marc Gravell

Answer 8

问题在于排序算法未指定，或者说是否为稳定排序算法不确定。

考虑以下浮点数数组：

[ 0.2 0.2 0.2 0.2 0.2 ]

总和为1。整数数组应该是：

[ 0 0 0 0 1 ]

然而，如果排序算法不稳定，它可能会将“1”排序到数组的其他位置...

- Vilx-

---

在这个意义上，它应该是一个稳定的排序。[0 0 0 0 1] 将是期望的结果。规则4的目的是表明 [0 0 0 1 0] 是不可接受的。（虽然这是个好观点） - David Z

Answer 9

以下是@mikko-rantanen代码的Python和Numpy实现。我花了一点时间来整理这个，所以尽管这个主题有些老旧，但这可能对未来的谷歌用户有所帮助。

import numpy as np
from math import floor

original_array = np.array([1.2, 1.5, 1.4, 1.3, 1.7, 1.9])

# Calculate length of original array
# Need to substract 1, as indecies start at 0, but product of dimensions
# results in a count starting at 1
array_len = original_array.size - 1 # Index starts at 0, but product at 1

# Calculate expected sum of original values (must be integer)
expected_sum = np.sum(original_array)

# Collect values for temporary array population
array_list = []
lower_sum = 0
for i, j in enumerate(np.nditer(original_array)):
    array_list.append([i, floor(j), j - floor(j)]) # Original index, lower bound, roundoff error
# Calculate the lower sum of values
lower_sum += floor(j)

# Populate temporary array
temp_array = np.array(array_list)

# Sort temporary array based on roundoff error
temp_array = temp_array[temp_array[:,2].argsort()]

# Calculate difference between expected sum and the lower sum
# This is the number of integers that need to be rounded up from the lower sum
# The sort order (roundoff error) ensures that the value closest to be
# rounded up is at the bottom of the array
difference = int(expected_sum - lower_sum)

# Add one to the number most likely to round up to eliminate the difference
temp_array_len, _ = temp_array.shape
for i in xrange(temp_array_len - difference, temp_array_len):
    temp_array[i,1] += 1

# Re-sort the array based on original index
temp_array = temp_array[temp_array[:,0].argsort()]

# Return array to one-dimensional format of original array
array_list = []
for i in xrange(temp_array_len):
    array_list.append(int(temp_array[i,1]))
new_array = np.array(array_list)

- ninetynine

---

在我在问题中提供的脚本中，还有一个Python实现。 - David Z

为什么我之前没看到这个 - 这本来可以节省我一些时间。;) 不过非常有帮助，谢谢！ - ninetynine

Answer 10

计算 向下取整之和 和 数字之和。 将 数字之和 四舍五入，然后减去 向下取整之和，差值即为需要修补的天花板数量（需要多少个 +1）。 按照其天花板与数字之间的差异从小到大对数组进行排序。

对于 diff 次（diff 是需要修补的天花板数量），我们将结果设置为 数字的天花板。其他情况下，将结果设置为 数字的向下取整。

public class Float_Ceil_or_Floor {

public static int[] getNearlyArrayWithSameSum(double[] numbers) {

    NumWithDiff[] numWithDiffs = new NumWithDiff[numbers.length];
    double sum = 0.0;
    int floorSum = 0;
    for (int i = 0; i < numbers.length; i++) {
        int floor = (int)numbers[i];
        int ceil = floor;
        if (floor < numbers[i]) ceil++; // check if a number like 4.0 has same floor and ceiling
        floorSum += floor;
        sum += numbers[i];
        numWithDiffs[i] = new NumWithDiff(ceil,floor, ceil - numbers[i]);
    }

    // sort array by its diffWithCeil
    Arrays.sort(numWithDiffs, (a,b)->{
        if(a.diffWithCeil < b.diffWithCeil)  return -1;
        else return 1;
    });

    int roundSum = (int) Math.round(sum);
    int diff = roundSum - floorSum;
    int[] res = new int[numbers.length];

    for (int i = 0; i < numWithDiffs.length; i++) {
        if(diff > 0 && numWithDiffs[i].floor != numWithDiffs[i].ceil){
            res[i] = numWithDiffs[i].ceil;
            diff--;
        } else {
            res[i] = numWithDiffs[i].floor;
        }
    }
    return res;
}
public static void main(String[] args) {
    double[] arr = { 1.2, 3.7, 100, 4.8 };
    int[] res = getNearlyArrayWithSameSum(arr);
    for (int i : res) System.out.print(i + " ");

}

}

class NumWithDiff {
    int ceil;
    int floor;
    double diffWithCeil;
    public NumWithDiff(int c, int f, double d) {
        this.ceil = c;
        this.floor = f;
        this.diffWithCeil = d;
    }
}

- Jerry Z.