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

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

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

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

источник

2012-02-01 Buttons840

Я получаю '[7, 5, 5]' как выход для первого фрагмента. – Blender

Я тоже, но первый кусок не выполним - его минимальные 11, всего 10. Я думаю, что последний кортеж в первом вызове должен был быть (2, 4). – AdamKG

@AdamKG - Правильно, я обновил последний кортеж в первом вызове (2,4) вместо (2,5). Я изменил некоторые значения, чтобы получить хороший пример, и не обновлял этот кортеж. – Buttons840

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

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

источник

2012-02-01 22:26:05 ElKamina

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

ответ

Смежные вопросы