Для приложения я хочу найти способ минимизировать, штрафуя общее пустое пространство в конце каждой строки абзаца. У меня есть набор слов W = [w1, w2, w3, ..., wn], составляющих текст, который я хочу содержать в абзаце, и каждое слово wi имеет соответствующую длину li. Я также знаю максимальное количество символов, включая пробелы, которое может поместиться в строке: m. Я не могу зашифровывать слова.
В этой ситуации я определил отношение, которое описывает стоимость пустого места в строке, начинающейся со слова i и заканчивающейся словом j, задается как c(i, j) = (m - (j - i) - sum_{k=i}^{k = j}lk)^3. Таким образом, c(i, j) должно быть положительным, иначе мне нужно разбить строку, а если j = n, я не штрафую за пустое место в последней строке: c(i, n) = 0.
С этими параметрами я нашел алгоритм, который минимизирует стоимость каждой линии перед переходом к следующей и вычисляет общую стоимость. Однако минимизация стоимости каждой линии не обязательно означает минимизацию общей стоимости.
Любой процесс, который я могу придумать, который минимизирует общую стоимость, требует огромного количества перестановок количества слов в каждой строке и, следовательно, не может быть реализован. Любые идеи жизнеспособного алгоритма для расчета минимальной стоимости?
