Problem 8 Solution: "Focus Fire!"

Let G(i,j) be the best possible expected damage using j models in groups of no more than i each.

First, we know that G(1,j) = j*F(1) for all j, because with groups of no more than 1, you just have j groups of 1.

We will now show how to calculate the values of G(i,*) from the values of G(i-1,*). (the * means all the numbers from 1 to n). Consider a grouping of j models in groups of no more than i, and let x equal the number of groups of size exactly i that it has. Thus the rest of the grouping is a grouping of (j-xi) models in groups of size no more than i-1. Thus the best you can do with this part of the grouping is G(i-1, j-xi). So the best possible expected damage total with x groups of size i is xF(i)+G(i-1, j-xi). If you already know the latter values, then you can simply compute this for all possible values of x to find out what the optimal value of x to choose is.

In this way you can construct the entire table of G(i,j) values where 1 <= i,j <= n by starting with i=1 and working your way upward. With each value of G(i,j) you also keep track of what grouping achieves that value. Then the grouping associated with G(n,n) is the result.

This technique of building up the solution to a complete problem (in this case the overall optimal grouping) from a series of solutions to subproblems (in this case the optimal groupings of smaller sets of models with limits on the maximum number per group) is known as dynamic programming, and is commonly used in algorithms to solve many different problems.

Another bit of trivia: the "groupings of N models" we've been talking about (like grouping a unit of 8 into groups of 3, 3, and 2) are known in combinatorics as partitions of N. The section we just finished in my combinatorics class had a significant part of it devoted to how to count up the number of partitions of N that satisfy different constraints, like no number repeated, maximum number less than 3, numbers can have "colors" associated with them, etc.