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

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

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

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

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


python algorithm greedy non-greedy
person Buttons840    schedule 01.02.2012    source источник
comment
Я получаю [7, 5, 5] в качестве вывода для первого фрагмента.   -  person Blender    schedule 02.02.2012
comment
Я тоже, но первый кусок невыполним - у него минимумов всего 11, а предусмотрено только 10. Я думаю, что последний кортеж в первом вызове должен был быть (2, 4).   -  person AdamKG    schedule 02.02.2012
comment
@AdamKG - Правильно, я обновил последний кортеж в первом вызове, чтобы он был (2,4) вместо (2,5). Я менял некоторые значения, чтобы получить хороший пример, и не обновлял этот кортеж.   -  person Buttons840    schedule 02.02.2012
comment
На этот вопрос нет ответа. Вам необходимо указать политику распространения available - sum(minima).   -  person John Machin    schedule 02.02.2012
comment
@JohnMachin - Использование весов. Я предполагаю, что вопрос в том, будете ли вы распределять оставшиеся значения в зависимости от того, кто имеет наибольший дефицит по минимальным значениям, или просто распределяете оставшиеся значения в зависимости от веса, игнорируя минимальные значения. Есть несколько разных политик, которые я могу придумать, но я не уверен, что предпочитаю.   -  person Buttons840    schedule 02.02.2012

Ответы (1)


arrow_upward
1
arrow_downward

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

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
person ElKamina    schedule 01.02.2012