Distributing objects on containers

64 Views Asked by At

Suppose we have $n$ containers, each has the ability of holding $f_{i}$ object for $i=1, 2, \dots, n$. That means $f_{i}$ is the maximum number of object that the $i$th container can hold.

Now, we have $N$ objects in total. We assume that $\displaystyle \sum_{i=1}^{n} f_{i} > N$ such that all $N$ objects can actually be filled into the containers.

Question: How to distribute these objects to the containers such that each container would not reach to its upper limit too quickly?

If $f_{i} \equiv f$ for all $i$, then my intuition told me that the $N$ objects must be uniformly distributed to the containers. (seems related to entropy). But what if all $f_{i}$ are different? What is the objective function?

1

There are 1 best solutions below

7
On

If you want to maximize the time until any bin reaches its maximum limit.

At any moment of time, when we want to insert an object, look for a bin with at least $2$ slots left.

That way, if $N\le \sum_{i=1}^nf_i-n-1$, the upper limit for every bin is not attained.

If $N \ge \sum_{i=1}^nf_i-n$, then we don't have a choice but let one of the bin attain the maximum.