algorithm - 将 float 转换为具有给定总和的整数

Question

我想将 float 组转换为整数数组。整数应总和为给定值，并且它们的值应类似于缩放的输入数组。

也就是说，完美的结果是通过input_float/sum_of_floats * target_sum计算出来的。示例:给定 float 0.1, 0.2, 0.5 和目标总和 16，输出应为 2, 4, 10。

遗憾的是，这些数字在现实中并没有那么好，所以我希望与实值的完美结果相比，将误差最小化。

例如，如果目标是 17，则它应该是 2, 4, 11。第一个 float 转换为 0.1/0.8 * 17 = 2.125。第二个和第三个对应于 4.25 和 10.6。显然，10.6 应该四舍五入。

但是，仅在 0.5 边界处四舍五入并不总是足够的。首先，存在将输入1, 1缩放为和3的病态情况:其中一个值必须为2，另一个为1，因此有两个等价的解决方案。

其次，我们可能需要进行不同的舍入:给定 0.1, 0.1, 0.3 和目标 8，我们得到 0.1/0.5 * 8 = 1.6 => 2 和 0.3/0.5 * 8 = 4.8 => 5，总和为 2 + 2 + 5 = 9 而不是 8。

这个例子的好的解决方案是什么？想到这些:

• 1, 1, 6
• 1, 2, 5
• 2, 2, 4

从 1.6 - 1 等我们看到第一个有绝对错误 0.6, 0.6, 1.2。我通常想对它们进行平方和求和，所以我们得到:

• 1, 1, 6 -> (1.6 - 1)^2 + (1.6 - 1)^2 + (4.8 - 6)^2 = 0.36 + 0.36 + 1.44 = 2.16
• 1, 2, 5 -> (1.6 - 1)^2 + (1.6 - 2)^2 + (4.8 - 5)^2 = 0.36 + 0.16 + 0.04 = 0.56
• 2, 2, 4 -> (1.6 - 2)^2 + (1.6 - 2)^2 + (4.8 - 4)^2 = 0.16 + 0.16 + 0.64 = 0.96

因此，1, 2, 5(或2, 1, 5)应该是首选。

我实现了一个近似求解器，它根据剩余空间(目标总和减去当前总和)来缩放值，这在大多数情况下都可以正常工作。我相信这是现有良好解决方案的常见问题，而不是对其进行改进。但是，我找不到它 - 你能指点我吗？

我在 C/C++/C# 类语言中工作，但我只关心这里的通用算法。

Answer 1

这是政治学中一个研究得非常透彻的问题。也就是如何在不同值数的人群中按比例分配席位的问题。例如，我们遇到如何在各州之间分配国会席位和multiple methods have been used .

每种方法的权衡略有不同。有些人倾向于将更多整数分配给大桶。少一些。在政治背景下，我们通常希望每个人都有一些代表性。

您已选择最小化舍入误差的平方和。为此，我认为只需分配每个舍入下方的最小整数，然后根据您想要的小数部分对它们进行排序，并将剩余的舍入分配到顶部就足够了。

如果您试图最小化比率差异的平方和，您会得到截然不同的答案。