Distributing an amount as evenly as possible

Question

We have have a certain amount e.g. 300 units. This amount should be as evenly as possible distributed over 40 "slots". It would be easy if each slot would be the same - so it would be 7,5 at each slot. However, the slots vary in size and we cannot "fill in" there more than its "size" allows for e.g. if its only 5. What we cannot "fill in" we have to distribute more over the other ones.

I have some basic ideas but I am far away from being an expeRt and hope there is an easy way to solve this. As an example how this could look like. In array "a" the values stand for the maxima the slots can take. a[i] is the maximum of the i-th slot. "b" is what we have to distribute overall e.g. 300.

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

 # overall sum to distribute
 b <- 300

Maybe it is possible to sort the values in a increasing order and then one could use it by a double for loop. a[,2] becomes the column for the "filled in" amount.

 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.

I am not sure how I can put the both for loops together and if this is an adequate solution overall. Happy to hear your ideas. Thanks!

I don't follow. Where is the information on the size that each slot can take? Do you have that info separately? As in what each of the 40 slots can take. — Maiasaura, Jun 28 '12 at 23:56
array a says says how much each slot can take. b <- 300 is the sum we have to distribute overall on the slots. — Fabian Stolz, Jun 28 '12 at 23:59

flodel · Accepted Answer · 2012-06-29T01:10:47.357

First version, using a while loop:

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

This second version is a little harder to understand, but more elegant I feel:

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

score 1 · Answer 2 · answered Jun 29 '12 at 02:31

1

Here's another option:

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

answered Jun 29 '12 at 02:31

Aaron left Stack Overflow

36,704
7
77
142

Thanks for the ideads! Let's assume there is another limit about how much we can fill into the slot independend from the size of the slot. Sth. like a general filing in constraint. E.g. there is the last slot with 30, we have 25 remaining but we can fill in 20 at max. Then we have to put the 5 remaining into an seperate remainder slot. Probably we have to use a condition if the "filling in" goes over a maxium we have to add it to the remainder pool. However I am not sure how to create this. – Fabian Stolz Jun 29 '12 at 08:04
After looking again in the morning, I think this is the same idea as @flodel's second answer. – Aaron left Stack Overflow Jun 29 '12 at 12:21
@FabianStolz: Better to revise the question or ask a new one than to ask in a comment. In this case I think a new question is in order, though be sure to link back to this one. – Aaron left Stack Overflow Jun 29 '12 at 14:20
here is the link of the new question: http://stackoverflow.com/questions/11288900/r-distributing-an-amount-as-evenly-as-possible-ii Would be nice if sb can have a look at it. – Fabian Stolz Jul 02 '12 at 07:06

Distributing an amount as evenly as possible

2 Answers2

Linked