如何在保留总和的同时将浮点数舍入为整数？

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, 0, 0, 0, 0, 0, 0, 0, 1]
[0.4, 0.4, 0.4, 0.4, 9.2, 9.2]
    => [0, 0, 1, 1, 9, 9] is preferable
    => [0, 0, 0, 0, 10, 10] is acceptable
[0.5, 0.5, 11]
    => [0, 1, 11] is fine
    => [0, 0, 12] is technically not allowed but I'd take it in a pinch

回答评论中提出的一些优秀问题:

• 两个数组都允许重复的元素(虽然我也有兴趣听说只有当浮点数不包含重复时才有效的算法)
• 没有一个正确的答案 - 对于给定的浮点数输入数组,通常有多个int数组满足这四个条件.
• 我想到的应用程序是 - 这有点奇怪 - 在MarioKart游戏中向顶级终结者分发点数;-)从来没有真正玩过这个游戏,但在看别人的时候我注意到有24个点分布在前4名选手,我想知道如何根据完成时间来分配积分(所以如果有人以较大的领先优势完成积分,他们会得到更多的积分).游戏将点总数跟踪为整数,因此需要进行这种舍入.

---

对于好奇,这是我用来确定哪些算法有效的测试脚本.

Answer 1

您可以尝试的一个选项是"级联舍入".

对于此算法,您可以跟踪两个运行总计:到目前为止的一个浮点数,以及到目前为止的一个整数.要获得下一个整数,请将下一个fp编号添加到运行总计中,舍入运行总计,然后从舍入的运行总计中减去整数运行总计: -

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

Answer 2

这是一个应该完成任务的算法.与其他算法的主要区别在于,这个算法总是以正确的顺序对数字进行舍入.最小化舍入误差.

该语言是一些伪语言,可能源自JavaScript或Lua.应该解释一下.注意一个基于索引(对于循环,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")

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(之后将损失[i]设置为0).它很复杂,但我猜它有效.

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