Распределение целых чисел с использованием весов и минимальных значений? - PullRequest
Новая
       38

Распределение целых чисел с использованием весов и минимальных значений?

0 голосов
/ 02 февраля 2012

В подобном вопросе Я спросил, как распределить целые числа с использованием весов.Мне любопытно, как можно было бы подойти к этой проблеме, если бы было наложено минимальное значение для каждого «сегмента» распределения.Вводя минимальное значение, это кажется гораздо более сложной проблемой.Вот моя жадная попытка, которая не работает: 

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].

В качестве примечания, моя цель - распределить доступное пространство (ширину) по нескольким столбцам.Все столбцы имеют минимальный размер, необходимый для того, чтобы «обойти» и отобразить по крайней мере некоторые из их данных, а некоторые столбцы все больше нуждаются в пространстве по мере увеличения доступного пространства.Я упоминаю об этом как об одном реальном использовании этого алгоритма, но я не хочу, чтобы это было обсуждением дизайна GUI.

Каковы некоторые решения этой проблемы?Чем проще, тем лучше.

1 Ответ

1 голос
/ 02 февраля 2012

Сначала вы должны выделить минимальные суммы и соответственно обновить.Позже вы можете соответственно распределить оставшуюся сумму. 

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