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&lt;double&gt; boxWidths = [ … ];


And the output could be:

List&lt;int&gt; 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&lt;int&gt; 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 &amp; 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