Задача об аккуратном форматировании?

Question

[leventov]

В одном учебнике по программированию приведена задача: текст из n слов длин l_i, строка шириной M. Необходимо форматировать текст так, чтобы минимизировать сумму кубов свободных остатков ширины по всем строкам, кроме последней (формально — вывести k_j: индексы последнего слова каждой строки). Дано указание воспользоваться методами динамического программирования.


Никак не могу выделить в решении подструктуру. Буду благодарен, если кто-нибудь подскажет направление мысли.

Answer 1

[MikhailEdoshin]

Насчет подструктуры ничего сказать не могу, но это упрощенный алгоритм Кнута-Пласса о выключке абзаца, соответственно направление мысли — посмотреть их работу :) Из вики:

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]