如何根据权重分配整数？该怎么计算？

Question

我需要根据一些权重来分配一个数值。比如说，如果我的权重是1和2，那么我希望权重为2的那一列的值是权重为1的那一列的两倍。

我有一些Python代码来展示我想做的事情，以及遇到的问题：

def distribute(total, distribution):
    distributed_total = []
    for weight in distribution:
        weight = float(weight)
        p = weight/sum(distribution)
        weighted_value = round(p*total)
        distributed_total.append(weighted_value)
    return distributed_total

for x in xrange(100):
    d = distribute(x, (1,2,3))
    if x != sum(d):
        print x, sum(d), d

在上面的代码中，有很多情况是分配一个数值后，结果的总和和原来的数值不一样。举个例子，分配3，权重是(1,2,3)，结果是(1,1,2)，总和变成了4。

有什么简单的方法可以修复这个分配算法吗？

更新：

我希望分配后的值是整数。具体的整数怎么分配并不重要，只要它们的总和是正确的，并且尽量接近正确的分配就可以了。

（这里的正确分配指的是非整数的分配，我还没有完全定义“尽量接近”的意思。只要总和等于原来的值，可能会有几种有效的输出。）

Answer 1

最简单的方法是计算一个叫做“归一化比例”的东西。这个比例是指你所有权重的总和超过你想要的总数的那个倍数。然后，你只需要把每个权重都除以这个比例就可以了。

def distribute(total, weights):
    scale = float(sum(weights))/total
    return [x/scale for x in weights]

Answer 2

你需要以某种方式来分配四舍五入的误差：

Actual:
| |   |     |

Pixel grid:
|   |   |   |

最简单的方法是把每个真实值四舍五入到最近的像素，这样无论是起始位置还是结束位置都一样。所以，当你把块A的值从0.5四舍五入到1时，你也会把块B的起始位置从0.5改成1。这就相当于把块B的大小减少了0.5（实际上是“偷”了它的大小）。当然，这样的话，块B又会从块C那里“偷”大小，最终导致你得到：

|   |   |   |

那么，你还希望怎么把3分成3个整数部分呢？

Answer 3

按照预期分配第一份股份。现在你面临一个更简单的问题，因为参与者少了一个，而且可分配的金额也减少了。继续这个过程，直到没有参与者为止。

>>> def distribute2(available, weights):
...     distributed_amounts = []
...     total_weights = sum(weights)
...     for weight in weights:
...         weight = float(weight)
...         p = weight / total_weights
...         distributed_amount = round(p * available)
...         distributed_amounts.append(distributed_amount)
...         total_weights -= weight
...         available -= distributed_amount
...     return distributed_amounts
...
>>> for x in xrange(100):
...     d = distribute2(x, (1,2,3))
...     if x != sum(d):
...         print x, sum(d), d
...
>>>