Given a sequence of n word lengths, w1, w2, , wn, representing the lengths of words that make up a paragraph, and a line width W. We assume that each wi includes one space at the end of the word in its count (i.e., for the, w would be 4), and that W includes one extra space at the end of the line (i.e., for an actual line width of 80, specify W = 81). The basic constraint on word placement is that, if word i through j are placed on a single line, then wi + + wj <= W. In this case the number of extra spaces is X = W (wi + + wj). The penalty for extra spaces in a line is assumed to be X³. There is no penalty for extra spaces on the last line of the paragraph. The penalty for the paragraph is the sum of the penalties for individual lines. The problem is to break the n words into lines such that the penalty for the paragraph is minimized (note that you cannot change the order of the n words).

For example:

Assume a paragraph consists of the following words:

i: 1 2 3 4 5 6 7 8 9 10 11

wi: 6 4 7 9 4 5 4 10 3 7 4

Suppose W =17. The following is a way to break the words with a total penalty of 640.

Words: (1,2,3) (4,5) (6,7) (8,9) (10,11)

X: 0 4 8 4 0

Penalty: 0 64 512 64 0

The problem is to find an optimal way to break the words into lines with a minimum total penalty.