среднем алгоритм распределения Взвешенного

Question

У меня N ведра, каждое с нормированным весом Вт _я. Я хотел бы распространять $ x на каждое ведро по его весу. Каждый ковш имеет минимум $ (MIN _я) и максимум $ (MAX _я), что алгоритм должен выполнить. Минимальные и максимальные значения каждого ведра имеют приоритет над весами. Является ли эта проблема разрешимой в полиномиальное время и как выглядит алгоритм?

Пример:

4 ведра, A, B, C, D

А: Вт = 100, MIN = 0, MAX = 150

B: W _B = 100, MIN _B = 0, MAX _B = 60

С: Вт _C = 1, MIN _С = 20, MAX _С = 150

Д: Ш _D = 1, MIN _D = 30, MAX _D = 150

Итого $ = $ 150

Ожидаемый результат:

А: $ 50

В: $ 50

С: $ 20

D: $ 30

Обратите внимание, что С и D используют их минут и остальную часть долларов разделены поровну, потому что А и B имеют одинаковый вес.

Answer 1

Пусть z - действительный параметр. Мое понимание проблемы заключается в том, что вы хотите найти z таким образом, что когда ведро i распределяется max (MIN _i, min (MAX _i, W _i z)), сумма распределений равна x.

Вот алгоритм O (n log n) -time (есть, вероятно, линейно-временный, но если он существует, он, вероятно, будет более сложным). Интуитивно, что он делает, это увеличить z непрерывно, пока сумма распределений не будет равна x.

Производная суммы по z представляет собой сумму производных для каждого ведра.Производное ведра я равен 0 при г < а, то W _я для < г < Ь, то 0 при б < г, где а = MIN _я/Вт _я является первой критической точкой, и 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: Вычесть то, что является «текущим назначением» от идеала:

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

Шаг 4: Назначьте доллар/цент до самого низкого значения в шаге 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 и прекратить выделение бюджетов на ведро, которое достигает свою шапочку.