加权平均分配算法

Question

我有 N 个桶，每个桶的标准化权重为 W_i。我想按重量将 $x 分配给每个桶。每个桶都有一个最小 $(MIN_i) 和最大 $(MAX_i) 算法需要实现的。每个桶的最小值和最大值优先于权重。这个问题可以在多项式时间内解决吗？算法是什么样的？

示例：

4 个桶，A、B、C、D

A: W_A = 100, MIN_A = 0, MAX_A = 150

B: W_B = 100, MIN_B = 0, MAX_B = 60

C: W_C = 1, MIN_C = 20, MAX_C = 150

D: W_D = 1, MIN_D = 30, MAX_D = 150

总计 $ = $150

预期结果：

甲：50 美元

乙：50 美元

C: $20

D: 30 美元

请注意，C 和 D 使用了他们的最小值，其余的美元平分，因为 A 和 B 的权重相同。

Answer 1

令 z 为实参数。我对这个问题的理解是，你想找到 z 这样，当桶 i 被分配时 max(MIN_i, min(MAX_i, W_i z)),分配总和等于x.

这是一个时间复杂度为 O(n log n) 的算法（可能有一个线性时间算法，但如果它确实存在，它可能会更复杂）。直观上它所做的是不断增加 z，直到分配的总和等于 x。

z 中和的导数是每个桶的导数之和。桶 i 的导数对于 z < a 为 0，然后对于 a < z < b 为 W_i，然后对于 b < z 为 0，其中 a = MIN_i / W_i为第一个临界点，b = MAX_i / W_i 是第二个临界点。我们对这些临界点进行排序，然后追踪得到的分段线性函数。在Python 3中（有意避免一些Python成语）：

import collections

Bucket = collections.namedtuple('Bucket', ('weight', 'min', 'max'))
Event = collections.namedtuple('Event', ('key', 'i', 'derivative'))


def allocate(total, buckets):
  n = len(buckets)
  events = []
  derivative = 0
  residual = total
  derivatives = []
  for i in range(n):
    bucket = buckets[i]
    events.extend([Event(bucket.min / bucket.weight, i, bucket.weight),
                   Event(bucket.max / bucket.weight, i, 0)])
    residual -= bucket.min
    derivatives.append(0)
  events.sort()
  z = 0
  for event in events:
    if derivative > 0:
      w = z + residual / derivative
      if w <= event.key:
        z = w
        break
    residual -= derivative * (event.key - z)
    derivative -= derivatives[event.i]
    derivatives[event.i] = event.derivative
    derivative += derivatives[event.i]
    z = event.key
  allocations = []
  for i in range(n):
    bucket = buckets[i]
    allocations.append(max(bucket.min,
                           min(bucket.max,
                               bucket.weight * z)))
  return allocations

print(allocate(150,
               [Bucket(100, 0, 150),
                Bucket(100, 0, 60),
                Bucket(1, 20, 150),
                Bucket(1, 30, 150)]))
# [50.0, 50.0, 20, 30]
print(allocate(100,
               [Bucket(40, 42, 55),
                Bucket(40, 0, 100),
                Bucket(20, 0, 4)]))
# [48.0, 48.0, 4]

Answer 2

第 1 步：分配所有最低预算

in your example: 
( 0, 0, 20 ,30)

第 2 步：在没有边界的情况下计算理想分配：

in your example: 
(100/202)*150 =74
(100/202)*150 =74
(1/202)*150 = 0.74
(1/202)*150 = 0.74

第 3 步：从理想值中减去 "current assignment"：

in your example:
0 - 74 = -74
0 - 74 = -74
20 - 0.74 = 19.26
30 - 0.74 = 29.26

第 4 步：将 dollar/cent 分配给第 3 步中的最低值

in your example:
-74 is the lowest value
so just assign a dollar to the first one with the lowest value

第 5 步：重复第 3 步和第 4 步，停止向达到上限的桶分配预算。

加权平均分配算法

Weighted average distribution algorithm

algorithm

optimization

distribution