Максимизация алгоритма возврата каретки (жадный?)

Question

У меня недавно был вопрос с интервью следующим образом: Нам дается список слов, и мы хотим отформатировать их, чтобы максимизировать # возврата каретки, сохраняя # букв на линию в пределах диапазона.

Например, мы хотим, чтобы диапазон 5 - 10 (включительно) букв в каждой строке одно решение заключается в следующем:

 
hello (5) 
cat (3) 

Другой заключается в следующем:

 
hello cat (9) <- 1 for a space 

Таким образом, первое решение лучше, потому что у нас есть 1 возврат каретки против 0 во втором.

Если слово не подходит, оно должно быть размещено на новой строке. Например:

 
hello (5) 
people (6) 

Наглядно мне это кажется жадной проблемой алгоритма, где мы вернемся, как только мы встретим минимальное письмо за линии ограничения. Однако это кажется слишком простым, и теперь я начинаю сомневаться в себе, но я не могу придумать встречный пример, где жадный не самый лучший.

Answer 1

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

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

Сортировка слов в порядке убывания количества букв.

Присвоить одну линию друг с словами длиной> = 5.

Для слов длины < 5, это проблема обратных несколько бункеров бен подложек, в котором:
Контейнеров имеют минимальную емкость 5 и максимум емкость 10.
Вы должны поместить слова в бункеры таким образом, чтобы количество бункеров было максимально.

Это, по крайней мере, NP полная проблема, но «я думаю» (тем более, что это было задано в интервью), можно подумать о динамической формулировке программирования, которая решает ее в псевдополиномиальное время (например, проблему с рюкзаком) ,

EDIT: IMO жадный алгоритм должен работать в том случае, если максимальная емкость не менее удвоенной минимальной емкости, как в этом случае.