Алгоритм максимального количества возвратов каретки (жадный?)

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

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

hello (5)
cat (3)

Другое это:

hello cat (9) <- 1 for a space

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

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

hello (5)
people (6)

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


algorithm greedy
person DillPixel    schedule 26.11.2013    source источник
comment
Почему у вас минимальный диапазон (5 из 5-10), если вы позволяете кошке (три буквы) быть в своей строке?   -  person justhalf    schedule 26.11.2013
comment
Я не учел этого... Я предположил, что последнее слово не находится под этими ограничениями. Но если она есть, то жадничать, наверное, не получится...   -  person DillPixel    schedule 26.11.2013
comment
Я думаю, что в диапазоне не должно быть минимума. В противном случае этот случай неразрешим: лягушка-бык ест лягушку-быка. Еда не сможет быть соединена ни с одним словом, не нарушая максимум 10 символов. Если вход не ограничен, чтобы всегда иметь решение с учетом условия диапазона.   -  person justhalf    schedule 26.11.2013

Ответы (1)


arrow_upward
1
arrow_downward

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

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

Расставь слова по убыванию количества букв.

Назначьте по одной строке словам длины >= 5.

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

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

РЕДАКТИРОВАТЬ: IMO, жадный алгоритм должен работать в случае, когда максимальная емкость как минимум равна удвоенной минимальной емкости, как в этом случае.

person Abhishek Bansal    schedule 26.11.2013
comment
Может быть, я не совсем понял, но слова должны быть отформатированы по порядку. Если нам даны слова «привет», «мир», «кошка», возврат каретки должен быть размещен таким образом, чтобы этот порядок сохранялся. - person DillPixel; 26.11.2013
comment
@DillPixel В этом случае это простой жадный подход, который даст вам решение, потому что нет причин, по которым вы бы не разместили возврат каретки как можно раньше в последовательности. - person Abhishek Bansal; 26.11.2013