# 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.

### More Insights

 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.

# First C Compiler Now on Github

The earliest known C compiler by the legendary Dennis Ritchie has been published on the repository.

# HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

# Building Bare Metal ARM Systems with GNU

All you need to know to get up and running... and programming on ARM

# Amazon's Vogels Challenges IT: Rethink App Dev

Amazon Web Services CTO says promised land of cloud computing requires a new generation of applications that follow different principles.

# How to Select a PaaS Partner

Eventually, the vast majority of Web applications will run on a platform-as-a-service, or PaaS, vendor's infrastructure. To help sort out the options, we sent out a matrix with more than 70 decision points to a variety of PaaS providers.

More "Best of the Web" >>