Динамическое программирование: минимизация пробелов

Question

Это вопрос домашней работы, но я полностью потерян. У меня есть невозможное время выяснить, что такое подзадача: я пробовал жадный подход, я пытался увеличить количество слов на линии и т. Д., И я ничего не могу придумать. Может ли кто-нибудь предложить любую проницательность?

Проблема: рассмотрите программу, которая преобразует список слов в текст шрифта. Программа печатает слова на строках длины W так, что количество дополнительных пробелов в конце строки так, что строка, содержащая слова с i по j, содержит W - j + i - SUM (символы в словах i через j). Напишите алгоритм динамического программирования, который минимизирует сумму квадратов дополнительных пробелов в каждой строке.

Answer 1

Я считаю, что подход вы должны иметь следующий:.

-> найти лучшее решение для линии длиной 1 и сохранить значение (это должно быть тривиальной).

-> найти лучшее решение для линии длиной 2 таким образом:

для каждого слова увидеть, если они подходят. если они вычисляют оставшееся пространство и используют наилучшее решение для этого пространства (останется 1 или 0 пробелов слева).

... (сделать это вплоть до W)

-> найти лучшее решение для линии длиной W таким образом:

для каждого слова увидеть, если они подходят. Если это так, вычислите оставшееся пространство и используйте лучшее решение для этого оставшегося пространства (так как оно меньше W, вы уже рассчитали его.)

Answer 2

Динамическое программирование - хороший выбор для решения таких проблем простым способом разработчик.

Метод динамического программирования, который мы можем использовать для решения этой проблемы, заключается в следующем. Во-первых, если все слова соответствуют одной строке, то мы закончили. Если нет, то мы попробуем все возможные комбинации, которые могли бы поместиться на этой одной строке, затем мы решаем подзадачу, состоящую из оставшихся слов для каждой возможной комбинации, мы можем найти лучший макет, минимизируя стоимость первого и добавив минимальную сумму стоимости оставшейся подзадачи.

Пусть MAX (я) крупнейшим J, для которых , а это означает, что слово J может поместиться на строку, начинающуюся со словом я. Мы можем заполнить n-элементный массив затрат c, где c [i] - минимальная стоимость печати слов от i до n следующим образом: Если MAX (i) = n, то c [i] = 0 else:
Заполнение массива сверху донизу от n до 1 займет время O ((M/2) n), так как не более M/2 слова могут вписываться в одну строку. Требуемое пространство - O (n).