Channels ▼
RSS

Design

Approximate String Matches and Dynamic Problems


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.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video