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

Question

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

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

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

 # overall sum to distribute
 b <- 300 

Возможно, можно отсортировать значения в порядке возрастания, а затем использовать его в двойном цикле for. [,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.

Я не уверен, как можно соединить оба цикла for и является ли это адекватным решением в целом. Рад слышать ваши идеи. Спасибо!

Answer 1

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

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]
}