使用给定的总和将浮动转换为整数

Question

我想将一个浮点数组转换为一个int数组。整数应该总和到一个给定的值，它们的值应该与缩放的输入数组类似。

换句话说，完美的结果是由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边界处进行舍入并不总是足够的。首先，存在将输入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之间划分国会席位。

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

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

如果你试图最小化比率差异的平方和，你会得到一个非常不同的答案。

Answer 2

考虑下一个简单的方法：

让我们想要总和S。 缩放所有值，并为每个缩放的v制作一对Int(v), Frac(v)，计算int部分的总和 - 比如ISum，然后增加int部分的S-ISum对与最大的小数部分

Answer 3

您可能很高兴知道您就在最佳解决方案的门口。有两个基本步骤：

1. 确定最接近的直接缩放解决方案，高于或低于所需的目标总和。您的帖子显示您已掌握此部分。
2. 出于说明的目的，我们假设您仍然将目标总和减去2（整数差异）。现在，您将解决方案整数循环2次（每个差异单位一个）。您需要找到可以添加1的元素，其中“goodness”度量标准的增加最少（幸运的是，具有所有正确的数学属性，使其成为可分离的迭代解决方案）。将1添加到一个元素，然后再循环并再次执行（在某些情况下，可能是具有多种值的相同元素）。

这会让你找到解决方案吗？

Answer 4

1. 计算浮点理想值。
2. 通过向下舍入到整数来创建候选值。
3. 而候选人的总和<目标 将具有最大误差的候选者增加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