Для приложения я хочу найти способ минимизировать, штрафуя, общее пустое пространство в конце каждой строки абзаца. У меня есть набор слов 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.
С этими параметрами я нашел алгоритм, который минимизирует стоимость каждой строки перед переходом к следующей и вычисляет общую стоимость. Однако минимизация стоимости каждой линии не обязательно означает, что общая стоимость также минимизирована.
Любой процесс, который я могу придумать, который минимизирует общую стоимость, требует огромного количества перестановок количества слов в каждой строке и, следовательно, не может быть реализован. Есть идеи жизнеспособного алгоритма для расчета минимальной стоимости?