Форум программистов, компьютерный форум CyberForum.ru

Динамическое программирование. Задача об абзаце - C++

Восстановить пароль Регистрация
 
Meny
0 / 0 / 0
Регистрация: 12.12.2013
Сообщений: 11
05.03.2014, 14:25     Динамическое программирование. Задача об абзаце #1
Всем доброго времени суток! Имеется задача:
Есть абзац текста, в котором много слов (блоков) с разными высотами, например обычные слова и математические формулы. Абзац достаточно длинный, поэтому его нужно разбить на строки. Высота строки определяется по наивысшему из блоков в ней. Высота абзаца определяется как сумма высот всех строк. Длина каждой строки определяется как суммарная ширина блоков, включенных в эту строку (пробелы не учитываются). Возможность разбиения блока для переноса со строки на строку не рассматривается. Изменять порядок следования блоков нельзя.
Нужно найти такое разбиение абзаца на строки, чтобы высота абзаца была минимальной.
Вход. Первая строка текста содержит ширину области печати (т.е. максимальную допустимую длину строки) и число N (количество блоков в абзаце), где 5<N<200; следующие N строк по два числа (ширину и высоту блока); все размеры натуральные числа не больше 1000000.
Выход. В первую строку текста вывести полученную высоту абзаца, во вторую количество строк М, на которые нужно разбить абзац, в следующие N строк количества блоков в соответствующих строках абзаца.

Необходимо решить тремя способами:
  • при помощи рекуррентного спуска
  • с использованием динамического программирования
  • модификация первой, основанная на механизме «запоминания»

Не прошу кидать готовый код, кто может, просто подскажите примерный алгоритм решения, что нужно сделать? Какую лучше оптимальную подзадачу выделить? и еще вопрос: что такое рекуррентный спуск? Заранее благодарен!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.03.2014, 14:25     Динамическое программирование. Задача об абзаце
Посмотрите здесь:

Задача на динамическое программирование. C++
C++ Динамическое программирование, задача "Уменьшение числа"
C++ Задача на динамическое программирование(скорее всего) (сколькими способами в сумме получить N, без подряд идущих одинаковых чисел)
C++ Динамическое программирование!
Задача о НОП (динамическое программирование) C++
C++ Задача на динамическое программирование
Задача "Движение по клеткам таблицы" (Динамическое программирование) C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 21:22. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru