使用权重和最小值分配整数？

Question

在一个类似的问题中，我问过如何根据权重来分配整数。我很好奇，如果对每个分配“桶”设定一个最小值，应该如何解决这个问题。设定最小值后，这个问题似乎变得更复杂了。以下是我尝试的贪心算法，但并没有成功：

def distribute(available, weights_and_mins):
    distributed_amounts = []
    total_weight = sum([i[0] for i in weights_and_mins])
    for weight, minimum in weights_and_mins:
        weight = float(weight)
        p = weight / total_weight
        distributed_amount = round(p * available)
        if distributed_amount < minimum:
            distributed_amount = minimum
        distributed_amounts.append(distributed_amount)
        available -= distributed_amount
        total_weight -= weight
    return [int(i) for i in distributed_amounts]

print distribute(10, ((10,1), (2,5), (2,4)))
print distribute(1000, ((10,1), (2,5), (2,4)))

目前的分配结果是 [7, 5, 4]，总共是16，这比我们要分配的数值多出6。正确的输出应该是 [1, 5, 4]，因为这样满足了所有列的最小要求。随着我们要分配的数值增加，分配的结果应该越来越接近正确的权重分配。例如，当分配1000时，算法能够正确地将值分配为 [714, 143, 143]。

顺便提一下，我的目的是在几列之间分配可用的空间（宽度）。所有列都有一个最低的尺寸要求，以便“勉强”显示一些数据，而随着可用空间的增加，有些列对空间的需求更大。我提到这个是为了说明这个算法在现实生活中的一个应用，但我不想让这个讨论变成界面设计的讨论。

对此问题有什么解决方案吗？越简单越好。

Answer 1

你应该先分配最少的金额，然后根据情况进行更新。之后再把剩下的金额分配好。

prior_available = available
allocated = [i[1] for i in weights_and_mins]
available = available - sum(allocated)
if available < 0:
    The hell breaks loose
total_weight = float(sum([i[0] for i in weights_and_mins]))
for i in len(weights_and_min):
    v = round( weights_and_min[i][0]*prior_available/total_weight )
    nv = min( available, max(v-allocated[i],0) )
    allocated[i] += nv
    available -= nv