Распределение суммы как можно более равномерно

Question

У нас есть определенная сумма, например. 300 единиц. Эта сумма должна быть как можно более равномерно распределена по 40 слотам. Было бы легко, если бы каждый слот был бы таким же, поэтому в каждом слоте было бы 7,5. Однако слоты различаются по размеру, и мы не можем «заполнить» там больше, чем его «размер» позволяет, например, если его только 5. Что мы не можем «заполнить», мы должны распространять больше по сравнению с другими.

У меня есть некоторые основные идеи, но я далек от того, чтобы быть expeRt и надеюсь, что есть простой способ решить эту проблему. В качестве примера, как это могло бы выглядеть. В массиве «a» значения обозначают максимумы, которые могут занимать слоты. a [i] - максимум i-го интервала. «b» - это то, что мы должны распространять в целом, например. 300.

# developing slots and their "size" 
a <- rnorm(40,10,4) 
sum(a) 

# overall sum to distribute 
b <- 300 

Может быть, можно отсортировать значения в порядке возрастания, а затем можно было бы использовать его двойной цикл. a [, 2] становится столбцом для «заполненной» суммы.

for i in 1:40 
{a[i,2] <- a[1,2]*40 
b <- a [1,2]*40} 

for i in 2:40 
{a[i,2] <- a[1,2]*39 
b <- a[1,2]*39} 

etc. 

Я не уверен, как я могу объединить оба цикла, и если это адекватное решение в целом. Счастливый услышать ваши идеи. Благодаря!

Answer 1

Первая версия, используя время цикла:

optimal.fill <- function(a, b) { 
    stopifnot(sum(a) >= b) 

    d <- rep(0, length(a)) 
    while(b > 0) { 
    has.room <- a > 0 
    num.slots <- sum(has.room) 
    min.size <- min(a[has.room]) 
    add.size <- min(b/num.slots, min.size) 
    d[has.room] <- d[has.room] + add.size 
    a[has.room] <- a[has.room] - add.size 
    b <- b - num.slots * add.size 
    } 
    return(d) 
} 

Это вторая версия является немного сложнее понять, но более изящным я чувствую:

optimal.fill <- function(a, b) { 
    stopifnot(sum(a) >= b) 

    slot.order <- order(a) 
    sorted.sizes <- a[slot.order] 
    can.fill  <- sorted.sizes * rev(seq_along(a)) 
    full.slots <- slot.order[which(cumsum(can.fill) <= b)] 

    d <- rep(0, length(a)) 
    d[ full.slots] <- a[full.slots] 
    d[!full.slots] <- (b - sum(a[full.slots]))/
        (length(a) - length(full.slots)) 

    return(d) 
} 

Answer 2

Вот еще один вариант:

optimal.fill2 <- function(a,b) { 
    o <- rank(a) 
    a <- sort(a) 
    ca <- cumsum(a) 
    foo <- (b-ca)/((length(a)-1):0) 
    ok <- foo >= a 
    a[!ok] <- foo[max(which(ok))] 
    a[o] 
}