Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

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

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

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

Задача на динамическое программирование - C++
Требуется решить задачу на динамическое программирование. Условия:На планете Олимпия очень популярна такая головоломка. На столе...

Задача на динамическое программирование. - C++
Что не правильно? #include &lt;fstream&gt; #include &lt;iostream&gt; using namespace std; int main() {

Задача о НОП (динамическое программирование) - C++
Здравствуйте!!! Мне нужно решить задачу о нахождении наибольшей общей подстроки. Поискал в интернете, нашёл такой код на Pascal: var...

Задача на динамическое программирование(скорее всего) (сколькими способами в сумме получить N, без подряд идущих одинаковых чисел) - C++
Дано число N&lt;106 и три числа A,B,C&lt;=N нужно вывести сколькими способами в сумме получить N, без подряд идущих одинаковых чисел(если N=3,...

Задача "Движение по клеткам таблицы" (Динамическое программирование) - C++
Хотел узнать, может у кого-нибудь в архивах есть подобная задача, которую можно будет использовать как шаблон к моей. Есть таблица NxM,...

Динамическое программирование, задача "Уменьшение числа" - C++
Имеется натуральное число N (1 &lt;= N &lt;= 106). За один ход с ним можно произвести следующие действия: Вычесть единицу Разделить на два ...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.03.2014, 14:25
Привет! Вот еще темы с ответами:

динамическое программирование - C++
Народ помогите плиз найти алгоритм решения следующей задачи. На посвящение в студенты собрались все первокурсники. Некоторые из них знают...

Динамическое программирование - C++
Столкнулся с такой задачей. Есть 6 фигурок площадью 3. Нужно узнать, сколькими способами можно полностью замостить ими поле n на m,...

Динамическое программирование - C++
Не понимаю динамических структур, списков, работы с ними. Посоветуйте источник изучения. Что-то вроде того что написано здесь...

Динамическое программирование - C++
Мячик прыгает по лестнице, состоящей из N ступенек, строго сверху вниз. За один прыжок он может отпрыгнуть на не более M ступенек....


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

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