Distributing integers using weights and minimum values?

Question

In a similar question I asked how to distributed integers using weights. I'm curious how one would approach this problem if a minimum value for each distribution "bucket" was imposed. By imposing a minimum value this seems to be a much more difficult problem. Here is my greedy attempt, which doesn't work:

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)))

Currently the values get distributed as [7, 5, 4], which is 16 which is 6 more than we have to distribute. The output should be [1, 5, 4] since this satisfies the minimum requirements for all columns. As the value we have to distribute grows, the distributions should be closer and closer to the correct weighted distribution. For example, by distributing 1000 the algorithm correctly distributes the values as [714, 143, 143].

As a side note, my purpose is to distribute available space (width) among several columns. All columns have a minimum size needed to "get by" and display at least some of their data, and some columns are more in need of space as the available space grows. I mention this as one real life use for this algorithm, but I don't want this to be a discussion of GUI design.

What are some solutions to this problem? The simpler the better.

Answer 1

You should first allocate minimum amounts first and update accordingly. Later you can allocate the remaining amount accordingly.

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