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

Динамическое программирование. Вложенные коробки. - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Как подсчитать количество вхождений подстроки в строку http://www.cyberforum.ru/cpp-beginners/thread229793.html
Добрый вечер! Как можно подсчитать количество вхождений строки S2 в строку S1? Допустим: S1= dfsgsffgsrr S2= gs
C++ Количество слов и цифр в строке, и последовательность Помогите, осталось решить всего 2 задачи из 10 заданных)) :) Нужно дописать решение, но чтобы его принимал компилятор BORLANDC, потому что сдаем пока только на нём. В первой задание: Сколько слов и цифр в строке? Написал, как найти количество слов, но как вычислите количество цифр? //254(3).cpp #include <stdio.h> #include <conio.h> enum {OUT, IN}; http://www.cyberforum.ru/cpp-beginners/thread229784.html
C++ Составить фрагмент программы
С коментприями, если можна!!!
C++ Составить программу
С коментприями
C++ Составить фрагмент программы http://www.cyberforum.ru/cpp-beginners/thread229756.html
С коментприями, если можна
C++ Составить фрагмент программы!!! С коментприями подробнее

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

Динамическое программирование. Вложенные коробки. - C++

16.01.2011, 21:38. Просмотров 2283. Ответов 8
Метки (Все метки)

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

Задача:
Даны N коробок в форме прямоугольных параллелепипедов
размерами ai*bi*ci. Некоторые из них, как правило, можно вложить в другие.

Толщина стенок коробок пренебрежимо мала, но строго больше нуля.
Коробки разрешается вращать, но только на углы, кратные 90° (иначе говоря, вкладывать коробки можно только "ровно", а не "наискось"). Коробки вкладываются "как матрешки", т.е. меньшая в среднюю, а средняя в большую, но нельзя вложить в большую коробку несколько маленьких рядом.

Среди заданных коробок необходимо выбрать такие, которые можно последовательно вложить одну в другую, причем их суммарный объем должен бытькак можно больше. Написать программу построения такой "цепочки" коробок. Если есть различные решения с одним и тем же максимальным суммарным объемом, вывести любое из них.

Помогите хотя бы советом...

Добавлено через 46 минут
Нашёл анализ задачи: Ясно, что при некоторых входных данных все коробки вложить

одну в другую невозможно. Например, ни одну из коробок 10×10x10 и 100×100x2

нельзя вложить в другую. Поэтому ниже слова "большая" и "меньшая" коробка бу-

дут означать, что "меньшую" можно разместить внутри "большей" (возможно, после

поворотов). Очевидно, что для ускорения проверки, помещаются ли коробки одна в

другой, можно предварительно отсортировать линейные размеры каждой коробки,

например, по неубыванию.

Эта задача уже упоминалась при сравнительном обсуждении достоинств алго-

ритмов решения задачи 13.3 (о подпоследовательности). Поэтому будем решать ее, опираясь на "N2" алгоритм решения задачи 13.3. Ясно, что при модификации ука

занного алгоритма сумму значений элементов следует заменить на сумму объеме*

коробок, а условие "ат<а" — на "т-я коробка помещается в к-ю". Но этого мало.

Пусть коробки таковы, что их можно последовательно вложить одну в другую.

И пусть в первый раз они задаются во входных данных в порядке от наименьшей до

наибольшей, а во второй раз — наоборот. Ответы в этих ситуациях должны совпа

дать, однако в первом примере все коробки окажутся вложенными, а во втором будет

взята одна наибольшая коробка. Ведь для задачи о монотонной подпоследователь-

ности важен порядок начальной последовательности, а для коробок — нет.

Естественно предположить: если порядок неважен, то при переборе it-подзадач в

процессе решения ти-подзадачи используются к не только от т+1 до N, но вообще все

возможные от 1 до N. Но что делать, если при решении текущей подзадачи нужен от-

вет еще не решенной подзадачи? Можно запускать рекурсию с запоминанием, но где

гарантия, что она не будет бесконечной?

Главная причина всех этих вопросов и сомнений кроется в том, что пока не выяс-

нено, как изменилась постановка серии подзадач*.

Итак, сформулируем серию подзадач, в которой т-подзадача будет иметь вид.

Найти Цепочку коробок с наибольшим суммарным объемом среди цепочек, в которых са-

мой внешней коробкой является т-я, а в качестве внутренних разрешается брать какие

угодно коробки набора.

После этого нетрудно заметить, что при решении любой /и-подзадачи могут по-

надобиться результаты решения только тех fc-подзадач, у которых k-я коробка поме-

щается в т-й.

Очевидно, что отношение вложенности коробок не может иметь циклов (когда

1л-я коробка помещается в «„-,-й, /2-я в 1,-й, а г,-я — в /л-й). Это позволяет пере-

упорядочить коробки так, чтобы "меньшие" всегда были размещены перед

"большими", и после такой предобработки описанная выше модификация алгорит-

ма из задачи 13.3 гарантированно даст правильный ответ.

Указанное переупорядочение является топологической сортировкой (см. подраз-

дел 8.3.3). Любое правильное решение этой задачи, основанное на рекурсии с запо-

минанием, будет неявно проводить топологическую сортировку, но в данной задаче

достаточно просто упорядочить коробки по неубыванию их объемов и затем решить

задачу итерационно. Подскажите как реализовать..

Добавлено через 12 минут
Мне уже к завтрому нужно

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