Optimal donut eating problem.

Question

There are 10 boxes of donuts sitting on a table. There are 10 donuts in each box. There are 30 flavors of donuts distributed randomly across the boxes.

I need to eat one of each flavor of donut. And I need to eat donuts from the minimum number of boxes.

How can I optimize this? Also, I know beforehand which donuts are in each box.

Answer 1

You need to eat from at least three boxes ($3\times10=30$ donuts), and may need to eat from all ten depending on how the 30 flavors are distributed and there are 967 such possible distributions.

This is not a large number so it should be sufficient to test as follows:

 SET = empty
 n = 3
 while not all flavors in SET do
   repeat
     test each n-element SET 
   until all flavors chosen or all n-element sets tested
   inc(n)
 end while
 return SET

If you want an approximate solution but need it very fast, then a greedy algorithm may get you a quicker result but will sometimes overestimate the number of boxes needed. But if the donuts are randomly distributed this won't be a problem often:

 SET = empty
 repeat
  add box with most untasted flavors to SET
 until all flavors chosen
 return SET

Answer 2

You have 30 values... $x_1, x_2...., x_30$ each of which is an integer at least equal to 1 such that:

$x_1 + x_2 ... x_30 = 100 $ here each c component represents the frequency of that flavor. Under ideal conditions these flavors would be distributed such that you need only sample from 3 boxes (minimum 30 donuts need to be sampled) but it is possible you need to check all 3 boxes.

Answer 3

Here is how a hungry teenager who is inept at mathematical symbolism would solve the problem. She would look at all the boxes and choose the one with the greatest number of flavors (if there is a tie, it does not matter which she chooses). Eat one of each of those flavors and then set that box aside. From the remaining boxes remove those donuts of the flavors that she has already eaten and give them to boys who wish they had this task. Now repeat this process with the remaining boxes. Repeat as needed. She should stop when she has eaten 30 donuts, all of which must be of distinct flavors. The boys can eat the rest of the donuts. Practical advice to the young girl: No one should eat this many donuts.

Answer 4

You can solve this problem with a binary programming problem.

Define $N_d$ as the number of donuts per box, $N_b$ as the total number of boxes and $N_f$ as the number of flavours. Also define $I=\{1,2,\ldots,N_d\}$, $J=\{1,2,\ldots,N_b\}$ and $K=\{1,2,\ldots,N_f\}$.

Furthermore, define donut $d_{ijk}$ to have the properties that it is donut $i$ in box $j$ and has flavour $k$, for $i\in I$, $j\in J$, $k\in K$.

Now, let $$x_{ijk}=\begin{cases}1,&\text{if donut $d_{ijk}$ is eaten}\\0,&\text{otherwise}\end{cases}$$ for $i\in I$, $j\in J$, $k\in K$. Also let $$y_j=\begin{cases}1,&\text{if box $j$ has been opened}\\0,&\text{otherwise}\end{cases}$$ for $j\in J$.

Your problem has $N_d=10$, $N_b=10$ and $N_f=30$.

The formulation is $$ \begin{align} \min Z=\sum\limits_{j\in J}y_j\\ {\text{such that}}&\\ \sum\limits_{i\in I}\sum\limits_{j\in J}x_{ijk}&\geq1\,\forall\,k\in K\tag{1}\\ \sum\limits_{i\in I}\sum\limits_{k\in K}x_{ijk}&\leq My_j\,\forall\,j\in J\tag{2}\\ x_{ijk},\,y_j&\text{ binary} \end{align} $$ In this formulation, $M$ is an arbitrary large number in (2) (in this case $M\geq N_dN_f$) to ensure that any donuts eaten in box $j$ marks that the box is opened. i.e. Any $x_{ijk}=1$ forces $y_j=1$. At least one donut of each flavour is eaten is ensured by (1).