What's an efficient algorithm to calculate line breaks (word wrap) for balanced widths (minimum raggedness)?

This is a real-world application, not a student assignment.

• Suppose we have some numbered boxes which are to be laid out, in order, from left to right, top to bottom, with no space between them, into a column of fixed width and infinite height.

• The boxes have the same height, but variable width.

• When a box doesn't fit, it should wrap to the next line (just like text).

• After that, we fix the number of lines, and then lay out the boxes again so that the lines have a more balanced width, which means they try to be the same width, as much as possible.

The input is, simply:

double colWidth = …;
List boxWidths = [ … ];

And the output could be:

List result = [ … ]; // Number of boxes in each line.
double minWidth = …;

An example: Suppose the column has width = 11, and 5 boxes have widths [2, 3, 5, 2, 1], then the layout is this:

| ** *** ***** |
| ** *         |

This means we can fit the boxes into 2 lines, and line widths differ a lot. One is 10 and the other is only 3 (difference is 7).

Now we have to lay them out again in 2 lines, to achieve balanced width:

| ** ***       |
| ***** ** *   |

The result is 2 boxes in the first line, and 3 boxes in the second line: List result = [2, 3]. Widths are now 5 and 8. Difference is 3, and minWidth is 8.

Please note, we cannot change their order. If we could, then the difference would be 1 and minWidth would be 7:

| ** *** *     |
| ***** **     |

My question:

What's the most efficient algorithm to solve this? I am interested in speed, and I don't care about memory usage.

Have you considered using the total-fit line breaking algorithm(a) used by TeX(b) and developed by Donald Knuth and Michael Plass?

• Donald Knuth and Michael Plass. "Breaking Paragraphs into Lines".

• https://github.com/jaroslov/knuth-plass-thoughts/blob/master/plass.md

• https://github.com/baskerville/paragraph-breaker

• https://cs.uwaterloo.ca/~dberry/ATEP/StudentLectures/Ananya.pdf

• https://news.ycombinator.com/item?id=1134342

• https://www.tug.org/TUGboat/tb21-3/tb68fine.pdf

• Remco Bouckaert. "A Probabilistic Line Breaking Algorithm".

Edit:

The total-fit line breaking algorithm has already been implemented in many languages, including Java:

• "Knuth & Plass line-breaking Revisited" in Java

• "The linebreaking algorithm of Knuth and Plass" in Java (via Generalized Knuth-Plass Linebreaking Algorithm)

• "rosettacode: Word wrap" has implementations of the Knuth Plass algorithm in a variety of languages

StackExchange Computer Science Q#123276, answer score: 12