0 like 0 dislike
6 views
In a textbook on programming given task: text of n words of lengths li, the line width M. you Must format the text so as to minimize the sum of the cubes of unencumbered balances of width for all the lines except the last one (formally derive kj: index of the last word of each line). Instructed to use methods of dynamic programming.

Can not allocate the substructure. I would be grateful if anyone tell me the direction of thought.
| 6 views

0 like 0 dislike
About substructure can not say anything, but this is a simplified algorithm of the Whip-Plasse about the justification of a paragraph, respectively, the direction of thought — see their work :) From wiki:
\r
Formally, the algorithm defines a value called badness associated with each possible line break; the badness is increased if the spaces on the line must stretch or shrink too much to make the line the correct width. Penalties are added if a breakpoint is particularly undesirable: for example, if a word must be hyphenated, if two lines in a row are hyphenated, or if a very loose line is immediately followed by a very tight line. The algorithm will then find the breakpoints that will minimize the sum of squares of the badness (including penalties) of the resulting lines. If the paragraph contains n possible breakpoints, the number of situations that must be evaluated naively is 2n. However, by using the method of dynamic programming, the complexity of the algorithm can be brought down to O(n2) (see Big O notation). Further simplifications (for example, not testing extremely unlikely breakpoints such as a hyphenation in the first word of a paragraph) lead to an efficient algorithm whose running time is almost always of order n. A similar algorithm is used to determine the best way to break paragraphs across two pages, in order to avoid widows or orphans (lines that appear alone on a page while the rest of the paragraph is on the following or preceding page). However, in general, a thesis by Michael Plass shows how the page breaking problem can be NP-complete because of the added complication of placing figures.[18]
by

0 like 0 dislike