Knuth–Plass line-breaking algorithm

A naive brute-force exhaustive search for the minimum badness by trying every possible combination of breakpoints would take an impractical O(2^n) time. The classic Knuth-Plass dynamic programming approach to solving the minimization problem is a worst-case O(n^2) algorithm but usually runs much faster, in close to linear time. Solving for the Knuth-Plass optimum can be shown to be a special case of the convex least-weight subsequence problem, which can be solved in O(n) time. Methods to do this include the SMAWK algorithm. == Simple example of minimum raggedness metric ==

For the input text AAA BB CC DDDDD with line width 6, a greedy algorithm that puts as many words on a line as possible while preserving order before moving to the next line, would produce: ------ Line width: 6 AAA BB Remaining space: 0 CC Remaining space: 4 DDDDD Remaining space: 1 The sum of squared space left over by this method is 0^2 + 4^2 + 1^2 = 17. However, the optimal solution achieves the smaller sum 3^2 + 1^2 + 1^2 = 11: ------ Line width: 6 AAA Remaining space: 3 BB CC Remaining space: 1 DDDDD Remaining space: 1 The difference here is that the first line is broken before BB instead of after it, yielding a better right margin and a lower cost 11. == References ==