1

同様の質問で、重みを使用して整数を分散する方法を尋ねました。各分布の「バケット」に最小値が課された場合、この問題にどのようにアプローチするのか興味があります。最小値を課すことにより、これははるかに難しい問題のように思われます。これが私の貪欲な試みですが、うまくいきません：

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]として配布されます。これは、配布する必要があるよりも6多い16です。出力は[1、5、4]である必要があります。これは、すべての列の最小要件を満たしているためです。分布しなければならない値が大きくなるにつれて、分布は正しい加重分布にますます近づくはずです。たとえば、1000を分散することにより、アルゴリズムは値を[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.

4

1 に答える 1

2

まず最初に最小金額を割り当て、それに応じて更新する必要があります。後で、それに応じて残りの金額を割り当てることができます。

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-01T22:26:05.677 に答える