Distribution of beans in jars to k members

Question

Here is the problem. We have N jars. Each jar can have any number of beans. These beans have to be distributed among C children. The resulting distribution should serve two goals Now

• the number of beans that each child gets must be the same (+/- 1 when total number of beans is not a multiple of C)

• each child to get all the beans from minimum number of distinct jars. Why? It is possible that beans in a jar may be contaminated. We want as few children to get infected as possible. E.g. if we have two jars with N beans each and two children, each child gets N beans. we would want child one to get N beans from jar 1 and child two to get beans from jar 2. As opposed to a solution, wherein child 1 gets half beans from jar 1 and half beans from jar 2. In former solution, if jar 1 is contaminated, only child 1 is infected. In latter solution, both children are infected.

So if

C = 5
beans = {B0:12, B1:12, B2:12, B3:12, B4:12} // Jar:<Bean-Count>

Distribution should be

{C1:{B0:12}, C1:{B1:12}, C2:{B2:12}, C3:{B3:12}, C4:{B4:12}}

Because each child has beans from exactly one jar. Following distribution will be less preferred

{C0:{B0:6, B1:6}, C1:{B0:6, B1:6}, C2:{B2:12}, C3:{B3:12}, C4:{B4:12}}

What will be the algorithm for achieving the distribution strategy with above goals in mind?

Answer 1

If this is a practical problem, it can be solved using integer linear programming (ILP).

We'll introduce three kinds of integer variables:

• $x_{i,j}$ counts the number of beans from jar $i$ that are given to child $j$.

• $y_{i,j}$ is 1 if child $j$ gets any beans from jar $i$, or 0 otherwise.

• $z_i$ is the number of children who get at least one bean from jar $i$.

Then we'll add some constraints to enforce the requirements in the question:

• $\lfloor B/C \rfloor \le \sum_i x_{i,j} \le \lceil B/C \rceil$ where $B$ is the total number of beans across all the jars. This ensures that each child receives the same number of beans.

• $0 \le x_{i,j} \le B_i y_{i,j}$, where $B_i$ is the number of beans in jar $i$, and $0 \le y_{i,j} \le x_{i,j}$. This ensures that $x_{i,j}$ and $y_{i,j}$ are consistent with each other.

• $\sum_j x_{i,j} \le B_i$. This ensures that you don't give out more beans from jar $i$ than are available.

• $z_i = \sum_j y_{i,j}$.

Finally, the objective function is the average of the $z_i$'s, i.e., $\frac{1}{N} \sum_i z_i$. We feed this to an integer linear programming solver and ask it to minimize the objective function, subject to the constraints above.

The worst-case running time of ILP solvers is exponential time, but in practice they are sometimes much more efficient than you might think. If you have $N,C < 50$, I suspect this might be efficient enough to work in practice. The only way to find out for sure is to try it.