将浮点数转换为具有给定总和的整数

Question

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

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

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

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

但是，仅在 0.5 边界处四舍五入并不总是足够的。首先是scaling input 1, 1 to sum 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）应该是首选。

我实现了一个近似求解器，它考虑剩余 space 剩余（目标总和减去当前总和）来缩放值，这大部分工作正常。我相信这是现有良好解决方案的常见问题，而不是对其进行改进。但是，我找不到它 - 你能指点我吗？

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

Answer 1

考虑下一个简单的方法：

让我们求和S。
缩放所有值，并且对于每个缩放的 v 生成一对 Int(v), Frac(v)，计算整数部分的总和 - 比如说 ISum，然后增加 S-ISum 对的整数部分与最大的小数零件

Answer 2

您可能会很高兴知道您已接近最佳解决方案。有两个基本步骤：

确定最近的直接缩放解决方案，高于或低于所需的目标总和。你的帖子说明你已经掌握了这部分.
为了便于说明，我们假设您的目标总和还差 2（整数差）。您现在循环遍历您的解决方案整数 2 次（每个差异单位一次）。您需要找到可以添加 1 且最少增加的元素 "goodness" 指标（幸运的是，它具有所有正确的数学属性使其成为一个可分离的迭代解决方案）。将 1 添加到一个元素，然后转回并再次执行（在某些情况下可能是相同的元素，具有广泛的值）。

这是否让您找到解决方案？

Answer 3

这是一个令人惊讶的政治研究问题。也就是如何在不同值数的人群中按比例分配席位的问题。例如，我们运行了解如何在各州之间分配国会席位和 multiple methods have been used。

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

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

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

Answer 4

计算浮点理想值。
通过向下舍入为整数创建候选值。
当候选人总和 < 目标
- 将错误最大的候选增加1

在python中：

   def convert(weights, target):
       ideals = [v/sum(weights) * target for v in weights]
       candidates = [int(math.floor(t)) for t in ideals]
       while (sum(candidates) < target):
            err = [(c-i)*(c-i) for c,i in zip(candidates, ideals)]
            candidates[err.index(max(err)]+=1
        return candidates

将浮点数转换为具有给定总和的整数

Convert floats to ints with given sum

algorithm

numeric