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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Очень странный баг http://www.cyberforum.ru/cpp-beginners/thread1111818.html
Вообщем такая история. Программировал в Visual studio, залез в чужую память и после этого не могу правильно считать данные из текстовых файлов. Написал новую программу с нуля - она тоже не правильно считывает. На другом компьютере тот же самый код работает правильно и считывает нормально (может проблема в библиотеке fstream?) Вот программа, по которой я тестирую поведение: #include "stdafx.h"...
C++ Определить значение двух последних разрядов двоичного числа Дано число в двоичном виде, нужно узнать значение двух старших разрядов этого числа. Подкиньте идейку или напишите кусок программы, как это можно реализовать. Заранее благодарю. http://www.cyberforum.ru/cpp-beginners/thread1111814.html
Даны массива a и b из n и m целых чисел, соответственно C++
Даны массива a и b из n и m целых чисел, соответственно. В каждом массиве - строго возрастающая последовательность чисел. Сформировать третий массив c, записать в него числа, которые есть хотя бы в одном из массивов a и b. Записывать только по 1 разу.
C++ Поменять местами минимальный и максимальный элемент в каждом столбце матрицы
Дано матрицу размером 5 x 10. Превратить матрицу, поменяв местами минимальный и максимальный элемент в каждом столбце.
C++ Вывести все строки матрицы, кратные 4 http://www.cyberforum.ru/cpp-beginners/thread1111797.html
Вывести все строки матрицы, кратные 4
C++ Найти средние арифметические значения элементов каждой строки Задать матрицу произвольным способом. Найти средние арифметические значения элементов каждой строки. подробнее

Показать сообщение отдельно
Meny
0 / 0 / 0
Регистрация: 12.12.2013
Сообщений: 11

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

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

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

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

Не прошу кидать готовый код, кто может, просто подскажите примерный алгоритм решения, что нужно сделать? Какую лучше оптимальную подзадачу выделить? и еще вопрос: что такое рекуррентный спуск? Заранее благодарен!
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru