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. A technique called dynamic programming works really well for this purpose. See if you can understand how.

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

Goal: Given four sizes 1, s1, s2, s3, 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 and s3, 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

Lets see in words what is happening: suppose that you are testing packet sizes 1, 5, 10, and 14. Initially, cost(1) = 1, cost(5) = 1, cost(10) = 1, and cost(14) = 1. All other costs are infinite. Now start with i = 2. At this point, cost(2) = infinity so the statement if cost(i) == infinite is true. We then look at j from 1 to 2 1. That leaves only j = 1 and we test whether cost(2) is greater than cost(1) + cost(2-1) = cost(1) + cost(1) = 1 + 1 = 2. Because cost(2) is currently infinite, that test succeeds. So cost(2) gets the value 2 (that is the meaning of cost(i) := (cost(j) + cost(i-j)) when i is 2 and j is 1) which is the cost of two single unit packets. See if you can continue the pattern.

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, then one good set of packet sizes is: 1 5 18 25 having an average cost of under 3.7 packets per request.

2. The same dynamic programming approach works for this problem, but the cost function has to change somewhat to reflect the change in likelihood for different size orders. One way to do so is to multiply the cost of orders between 10 and 20 (inclusive) by 4. That will reflect the increased frequency of those orders. To get the best average, divide the total cost by 113 (80 + (3*11)). Otherwise, nothing changes in the process. A good set of packet sizes (one of the best in fact) is 1, 10, 13 and 17. And the average required number of packets is under 3.5. Can you find any others?