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

Question

Мне нужно распределить значение, основанное на некоторых весах. Например, если мои весы равны 1 и 2, я бы ожидал, что столбец, взвешенный как 2, будет иметь в два раза больше значения, поскольку столбец с весом 1.

У меня есть код Python для демонстрации того, что я пытаюсь сделать, и проблема:

def distribute(total, distribution): 
    distributed_total = [] 
    for weight in distribution: 
     weight = float(weight) 
     p = weight/sum(distribution) 
     weighted_value = round(p*total) 
     distributed_total.append(weighted_value) 
    return distributed_total 

for x in xrange(100): 
    d = distribute(x, (1,2,3)) 
    if x != sum(d): 
     print x, sum(d), d 

Есть много случаев, показываемых выше, где распространение результатов стоимости в сумме распределения отличаться от другого, чем исходное значения кода. Например, распределение 3 с весами (1,2,3) приводит к (1,1,2), которое составляет 4.

Каков самый простой способ исправить этот алгоритм распределения?

UPDATE:

Я ожидаю, что распределенные значения быть целыми числами. Не имеет значения, как распределяются целые числа, пока они соответствуют правильному значению, и они «как можно ближе» к правильному распределению.

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

Answer 1

Распределите первую акцию, как ожидалось. Теперь у вас есть более простая проблема с одним меньшим количеством участников и уменьшенной суммой, доступной для распространения. Повторяйте, пока участников больше не будет.

>>> def distribute2(available, weights): 
...  distributed_amounts = [] 
...  total_weights = sum(weights) 
...  for weight in weights: 
...   weight = float(weight) 
...   p = weight/total_weights 
...   distributed_amount = round(p * available) 
...   distributed_amounts.append(distributed_amount) 
...   total_weights -= weight 
...   available -= distributed_amount 
...  return distributed_amounts 
... 
>>> for x in xrange(100): 
...  d = distribute2(x, (1,2,3)) 
...  if x != sum(d): 
...   print x, sum(d), d 
... 
>>> 

Answer 2

Если вы ожидаете распределяя 3 с весами (1,2,3) равным (0,5, 1, 1,5), то округление ваша проблема:

weighted_value = round(p*total) 

вы хотите:

weighted_value = p*total 

EDIT: Решение возвращать целое распределение

def distribute(total, distribution): 
    leftover = 0.0 
    distributed_total = [] 
    distribution_sum = sum(distribution) 
    for weight in distribution: 
    weight = float(weight) 
    leftover, weighted_value = modf(weight*total/distribution_sum + leftover) 
    distributed_total.append(weighted_value) 
    distributed_total[-1] = round(distributed_total[-1]+leftover) #mitigate round off errors 
    return distributed_total 

Answer 3

Самый простой подход заключается в расчете шкалы нормализации, что является фактором, с помощью которого сумма весов превышает сумму вы стремитесь, а затем разделить каждый элемент в вашем весов по этой шкале.

def distribute(total, weights): 
    scale = float(sum(weights))/total 
    return [x/scale for x in weights] 

Answer 4

Вы должны распространять ошибки округления как-то:

Actual: 
| | |  | 

Pixel grid: 
| | | | 

Простейшие будут округлить каждое истинное значение до ближайшего пикселя, и для начального и конечного положения. Итак, когда вы округлите блок A 0,5 до 1, вы также измените начальную позицию блока B от 0,5 до 1. Это уменьшает размер B на 0,5 (по сути, «крадя» размер от него). Конечно, это ведет к тому, B украсть размер от C, в конечном счете, в результате чего в том:

| | | | 

но как еще вы ожидали разделить 3 на 3 составные части?