使用权重和最小值分配整数？

发布于 2025-01-01 12:26:05 字数 1114 浏览 1 评论 0原文

在类似问题中，我问如何使用权重分配整数。我很好奇如果对每个分布“桶”施加最小值，人们将如何解决这个问题。通过施加最小值，这似乎是一个更加困难的问题。这是我的贪婪尝试，但行不通：

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 设计的讨论。

这个问题有哪些解决方案？越简单越好。

原文

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.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

自此以后，行同陌路 2025-01-08 12:26:05

您应该首先分配最低金额并进行相应更新。稍后您可以相应地分配剩余金额。

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

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

回复收藏 0 原文

~没有更多了~