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.

Me too, but the first chunk isn't satisfiable - his minimums total 11, only 10 are provided. I think the last tuple in the first call was supposed to be (2, 4). — AdamKG, Feb 01 '12 at 22:10
@AdamKG - Correct, I updated the last tuple in the first call to be (2,4) instead of (2,5). I was changing some values to get a good example, and didn't update that tuple. — Buttons840, Feb 01 '12 at 22:14
This question is unanswerable. You need to specify a policy for distributing `available - sum(minima)`. — John Machin, Feb 01 '12 at 22:29
@JohnMachin - Using the weights. I guess the question is would you distribute the remaining values based on who is the most deficit by the minimum values or just plain distribute the remaining values based on weight while ignoring the minimum values. There's a few different policies I can think of, but I'm not sure which I prefer. — Buttons840, Feb 01 '12 at 22:45

score 2 · Accepted Answer · answered Feb 01 '12 at 22:26

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

Distributing integers using weights and minimum values?

1 Answers1