Packing Donuts

The title of this column promises something sweet, so here goes. A certain gourmet donut shop prides itself on being able to provide its customers with any number of donuts between 1 and 80. A customer may go to the counter and say, "I want 43 donuts," and 43 donuts will appear in under a minute.

The shop wants to use five different-sized containers. Your job is to figure out what those sizes should be in order to minimize the number of packets needed to fill the average order.

To get you started on the problem, suppose the packet sizes are 1, 5, 10, 20, and 50. If someone orders 48 donuts, then the number of packets required is six: two packets of 20, one of 5, and three of 1.

One strategy to find the best packet sizes is to try all possible different combinations of five sizes and find the best. But think a little before you take that route. First, one of the sizes must be 1, so really, you have to test ascending quadruples of sizes between 2 and 80 only. When evaluating a quadruple, add a packet of size 1 to get a set of five packet sizes.

Warm-Up: Suppose the number of donuts in an order ranged only between 1 and 12 with equal probabilities of each order. If there were four packet sizes, what should they be to minimize the number of packets used to satisfy an order?

Solution to Warm-Up: An optimal set of packet sizes would be 1, 3, 5, and 6. We know this is optimal because no number requires more than two packets (e.g. an order of two requires two packets of one each and an order of 11 requires two packets one of size five and one of size six) and four require only one. No other set of packet sizes can be better.

The Puzzles

1. Assuming all orders between 1 and 80 are equally likely, what would be five packet sizes, so the number of packets given to a customer will be minimized on the average?

2. Suppose you wanted to be sure that no more than 4 packets are ever required for any order between 1 and n. What is the maximum n you can manage? What would the packet sizes be?

Solutions

The computational "inner loop" of this process is to calculate the average cost. That is, given a set of four packet sizes, compute the average number of packets needed for each order.

Here is high level pseudo-code of one dynamic programming method.

  
Goal: Given five sizes 1, s1, s2, s3, s4 find the cost per order.
  
 Create an array of size 80. This will be your cost array.
 Initialize each entry to have infinite cost except for the entries
at locations 1, s1, s2, s3, and s4 to which you assign a cost of 1.
  
 for entry i = 2 to 80
   if cost(i) == infinite
      for entry j from 1 to i-1
        if (cost(j) + cost(i-j)) < cost(i)
             cost(i) := (cost(j) + cost(i-j))
        end if
      end for
   end if
 end for
 sum all the costs and divide by 80 to get the average cost

Now that you see how to evaluate a given candidate set of packet sizes, it remains only to go through the different packet size triplet possibilities to find the best set of packet sizes.

1. When all quantities between 1 and 80 are equally likely, find the minimum average cost and the packet sizes that give you that.

It's possible to achieve an average of 3.15 packets per customer with packet sizes 1, 6, 9, 22, and 24.

2. For orders of 68 or less, no purchase requires more than 4 packets assuming packet sizes are 1, 3, 8, 18, and 29. I don't know how to do better.