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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Meny
0 / 0 / 0
Регистрация: 12.12.2013
Сообщений: 11
#1

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

05.03.2014, 14:25. Просмотров 408. Ответов 0
Метки нет (Все метки)

Всем доброго времени суток! Имеется задача:
Есть абзац текста, в котором много слов (блоков) с разными высотами, например обычные слова и математические формулы. Абзац достаточно длинный, поэтому его нужно разбить на строки. Высота строки определяется по наивысшему из блоков в ней. Высота абзаца определяется как сумма высот всех строк. Длина каждой строки определяется как суммарная ширина блоков, включенных в эту строку (пробелы не учитываются). Возможность разбиения блока для переноса со строки на строку не рассматривается. Изменять порядок следования блоков нельзя.
Нужно найти такое разбиение абзаца на строки, чтобы высота абзаца была минимальной.
Вход. Первая строка текста содержит ширину области печати (т.е. максимальную допустимую длину строки) и число N (количество блоков в абзаце), где 5<N<200; следующие N строк по два числа (ширину и высоту блока); все размеры натуральные числа не больше 1000000.
Выход. В первую строку текста вывести полученную высоту абзаца, во вторую количество строк М, на которые нужно разбить абзац, в следующие N строк количества блоков в соответствующих строках абзаца.

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

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

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

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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru