Алгоритм манипулирования строками

Question

Я читаю в массиве строк, таких как: ааа bb ccccc ddd eeee fffffff ggggggg. Мне нужна помощь в работе над алгоритмом, чтобы эти строки помещались на как можно меньших строках, при этом максимальное количество символов в строке является фиксированным значением, например 15. Если добавление другой строки к этой строке превышает это значение, мне нужно сделать новую строку.

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

Вывод, который мне нужен, будет выглядеть так:

ааа бб ддд ээээ fffffff ggggggg

Поскольку в каждой строке 15 символов, это наименьшее количество строк, которое вы можете иметь.

Я использую диез C.

Answer 1

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

Начните заполнять строку чанком символов (любого размера), если вы не можете вставить новое слово, проверьте, добавляется ли пропущенное слово«вместо» одного из слов в строке даст вам лучше заполнить цитату.если это так, замените, если не пропустите это слово, попробуйте новое.(под новым я подразумеваю другой размер, я предполагаю, что вы хэшируете все слова одинакового размера в одни и те же сегменты) после того, как вы перепробовали все размеры, вы можете перейти к следующей строке и сделать то же самое, однако вам также необходимо проверить,поменяв местами элементы между первой и второй строками, вы получите лучший «общий» результат.Реализовать это можно в n ^ 2, но это немного сложнее, если вам не важна вычислительная эффективность, просто сделайте это грубо.