Given a sequence of n word lengths, w1, w2, …, wn, representing the lengths of w
ID: 3864634 • Letter: G
Question
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 X3. 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.
Explanation / Answer
Lets taking the same example with i indicating word number and w[] be the array of words.
n be the total number of words,
sum be a counter to calculate the words
W be the one line width.
we will run a loop to get sum of the penalties:
int sum = 0;
for (int i=1 ; i < n ; i++)
{
if(sum < W)
{
sum = sum + w[i];
}
else
{
System.out.println("words break:"+w[i-1]);
}
}
This loop determines word breaks at each line. every next line starts with the new word break;
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.