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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.82
opax
 Аватар для opax
0 / 0 / 0
Регистрация: 29.03.2010
Сообщений: 21
16.01.2011, 21:38     Динамическое программирование. Вложенные коробки. #1
Необходимо написать три версии алгоритма для решения предложенной задачи.
• неэффективная, при помоши рекуррентного спуска.
• с использованием динамического программирования.
• модификация первой, основанная на механизме «мемоизации».

Задача:
Даны 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 минуты
пожалуйста,помогите..
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.01.2011, 21:38     Динамическое программирование. Вложенные коробки.
Посмотрите здесь:

C++ Динамическое программирование
Динамическое программирование C++
Динамическое программирование. C++
C++ ДП Динамическое программирование
C++ Динамическое программирование
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Merlin666
 Аватар для Merlin666
96 / 96 / 10
Регистрация: 26.12.2010
Сообщений: 220
16.01.2011, 21:51     Динамическое программирование. Вложенные коробки. #2
Вам понадобится метод анализа для данной коробки, помещается ли другая в нее..статический..что-то нечто:

C++
1
2
3
4
5
6
7
8
 static bool IsPlaced(box A, box B)
 {
   bool flag = false;
   
   if ((A.x>B.x)&&(A.y>B.y)&&(A.z>B.z)) flag = true;
 
   return flag;
 }
Но это без поворота одной коробки относительно другой..

Добавлено через 3 минуты
Ну и сортировочку сделать, составив массив коробок, сортировка по объему..)
opax
 Аватар для opax
0 / 0 / 0
Регистрация: 29.03.2010
Сообщений: 21
16.01.2011, 22:03  [ТС]     Динамическое программирование. Вложенные коробки. #3
спасибо, а посоветуйте как лучше хранить размеры коробок, номера и объемы.. чтобы динамически.. многомерные векторы?
Merlin666
 Аватар для Merlin666
96 / 96 / 10
Регистрация: 26.12.2010
Сообщений: 220
16.01.2011, 22:16     Динамическое программирование. Вложенные коробки. #4
Чтобы динамически-отличный выбор односвязный циклический или нециклический список..)
opax
 Аватар для opax
0 / 0 / 0
Регистрация: 29.03.2010
Сообщений: 21
16.01.2011, 22:22  [ТС]     Динамическое программирование. Вложенные коробки. #5
не могли бы вы накидать динамический способ реализации ?.. остальные попробую сам сделать..
Merlin666
 Аватар для Merlin666
96 / 96 / 10
Регистрация: 26.12.2010
Сообщений: 220
16.01.2011, 22:24     Динамическое программирование. Вложенные коробки. #6
Посмотрите тут http://www.dmtsoft.ru/bn/373/as/oneaticleshablon/
Просто нет компилятора под рукой=( в голове обрабатываю..)
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
17.01.2011, 09:08     Динамическое программирование. Вложенные коробки. #7
Цитата Сообщение от opax Посмотреть сообщение
не могли бы вы накидать динамический способ реализации ?..
Накидываю:
Создаете стурктуру коробки, которая включает в себя:
- длина стороны A
- длина стороны B
- длина стороны C (заполнять данных о сторонах нужно так: A - самое максимальное, B - меньше или равно A, С - меньше или равно B)
- объем коробки (вычисляется при заполнении из данных о сторонах) (V)
- номер индекса коробки с которой есть связь (далее подробней объясню) (Num)
- максимальный объем всех вложенных коробок (далее подробней объясню) (Max_V)
- номер самой коробки (нужно, если требуется в конце программы вывести номера коробок)
Далее можно так:
Создаем массив размером N (количество коробок) для хранения типа созданной структуры. Считываем данные в этот массив (длины сторон), расчитываем сразу объем коробок, при необходимости проставляем номера коробок.
Далее сортируем этот массив по убыванию сторон так:
if(mas[i].A<mas[i+1].A ||
(mas[i].A==mas[i+1].A && mas[i].B<mas[i+1].B)
|| (mas[i].A==mas[i+1].A && mas[i].B==mas[i+1].B && mas[i].C<mas[i+1].C))
// то меняем местами mas[i] и mas[i+1]
После сортировки делаем: mas[N-1].Max_V=mas[N-1].V; mas[N-1].Num=N;

Далее сама динамика. Перебираем элементы массива от N-2 до 0. Для каждого очередного элемента массива делаем следующее:
- mas[i].Num=N; mas[i].Max_V=mas[i].V;
- затем просматриваем элементы правее очередного. Если какой-то элемент помещается в очередной (это проверяется так: if(mas[i].A>mas[j].A && mas[i].B>mas[j].B && mas[i].C>mas[j].C)), и при этом mas[i].Max_V<mas[j].Max_V+mas[i].V , то делаем так: mas[i].Max_V=mas[j].Max_V+mas[i].V; mas[i].Num=j;
После этого прохода ищем элемент с максимальным значением mas[i].Max_V . Это и есть значение максимального суммарного объема. Что бы вывести коробки, которые вложены, используем значение mas[i].Num .
opax
 Аватар для opax
0 / 0 / 0
Регистрация: 29.03.2010
Сообщений: 21
17.01.2011, 09:35  [ТС]     Динамическое программирование. Вложенные коробки. #8
Спасибо огромное!



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

Прога не всегда работает правильно..
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.01.2011, 19:00     Динамическое программирование. Вложенные коробки.
Еще ссылки по теме:

C++ Динамическое программирование
Динамическое программирование C++

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

Или воспользуйтесь поиском по форуму:
opax
 Аватар для opax
0 / 0 / 0
Регистрация: 29.03.2010
Сообщений: 21
23.01.2011, 19:00  [ТС]     Динамическое программирование. Вложенные коробки. #9
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Накидываю:
Создаете стурктуру коробки, которая включает в себя:
- длина стороны A
- длина стороны B
- длина стороны C (заполнять данных о сторонах нужно так: A - самое максимальное, B - меньше или равно A, С - меньше или равно B)
- объем коробки (вычисляется при заполнении из данных о сторонах) (V)
- номер индекса коробки с которой есть связь (далее подробней объясню) (Num)
- максимальный объем всех вложенных коробок (далее подробней объясню) (Max_V)
- номер самой коробки (нужно, если требуется в конце программы вывести номера коробок)
Далее можно так:
Создаем массив размером N (количество коробок) для хранения типа созданной структуры. Считываем данные в этот массив (длины сторон), расчитываем сразу объем коробок, при необходимости проставляем номера коробок.
Далее сортируем этот массив по убыванию сторон так:
if(mas[i].A<mas[i+1].A ||
(mas[i].A==mas[i+1].A && mas[i].B<mas[i+1].B)
|| (mas[i].A==mas[i+1].A && mas[i].B==mas[i+1].B && mas[i].C<mas[i+1].C))
// то меняем местами mas[i] и mas[i+1]
После сортировки делаем: mas[N-1].Max_V=mas[N-1].V; mas[N-1].Num=N;

Далее сама динамика. Перебираем элементы массива от N-2 до 0. Для каждого очередного элемента массива делаем следующее:
- mas[i].Num=N; mas[i].Max_V=mas[i].V;
- затем просматриваем элементы правее очередного. Если какой-то элемент помещается в очередной (это проверяется так: if(mas[i].A>mas[j].A && mas[i].B>mas[j].B && mas[i].C>mas[j].C)), и при этом mas[i].Max_V<mas[j].Max_V+mas[i].V , то делаем так: mas[i].Max_V=mas[j].Max_V+mas[i].V; mas[i].Num=j;
После этого прохода ищем элемент с максимальным значением mas[i].Max_V . Это и есть значение максимального суммарного объема. Что бы вывести коробки, которые вложены, используем значение mas[i].Num .
не умею вообще со структурами работать можете написать код? буду очень благодарен..


полный перебор написал, скорость работы алгоритма O(n^2)..

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <fstream>//не помню какие библиотеки нужные
#include <stdio.h>// поэтому написал все что помню
#include <conio.h>
#include <stdlib.h>
#include <windows.h>
#include <vector>
#include <string.h>
#include <iomanip>
#include <algorithm>
using namespace std;
 
vector<pair<int,vector<int> > > sort_kzbra(vector<pair<int,vector<int> > > mas){
  int l = 0, r = mas.size()-1;
  while (l<=r)
  {
    // всплывает самый "легкий" элемент
    for (int i = r ;i>l;i--){
      if (mas[i-1].first<mas[i].first){
        swap(mas[i-1],mas[i]);}}
     
    l++;
    // тонет самый "тяжелый элемент"
    for (int i=l; i<r; i++){
      if (mas[i].first<mas[i+1].first){
        swap(mas[i],mas[i+1]);}}
   
    r--;
  }
return mas;
}
 
vector<int> sort(vector<int> mas)
{
  int l = 0, r = mas.size();
  while (l<=r)
  {
    // всплывает самый "легкий" элемент
    for (int i = r ;i>l;i--){
      if (mas[i-1]<mas[i]){
        swap(mas[i-1],mas[i]);}}
  
    l++;
    // тонет самый "тяжелый элемент"
    for (int i=l; i<r; i++){
      if (mas[i]<mas[i+1]){
        swap(mas[i],mas[i+1]);}}
   
    r--;
  }
  return mas;
}
int main()
{
vector<pair<int,vector<int> > > pgl;//массив для записи паралеугольников
int n;//размерность пространства
int i,j,k;
int dt;
int mv;//наибольшее кол-во вложимых паралеугольников
int mvv;//временное наибольшее
int mimo;
vector<int> spd;
pair<int,vector<int> > nul;//ноль
ifstream elif("input.txt");
 elif>>n;
 i=0;
 pgl.resize(0);
         while(!elif.eof()){
       pgl.push_back(nul);
              for (j=0;j<n;j++){
              elif>>dt;
              if (dt<0) dt=-dt;
           //   cout<<dt<<" ";
              pgl[i].second.push_back(dt);}
           //   cout<<endl;
         i++;}
for(i=0;i<pgl.size();i++){
    pgl[i].first=1;
        for(j=0;j<pgl[i].second.size();j++){
                pgl[i].first=pgl[i].first*pgl[i].second[j];}}
                
 
  pgl=sort_kzbra(pgl);//сортируем паралеугольники по объему(наибольший - в начале)
for(i=0;i<pgl.size();i++){pgl[i].second=sort(pgl[i].second);}//сортируем все стороны по неубыванию(их все равно крутить можно)
 
  for(i=0;i<pgl.size();i++){
    for(j=0;j<pgl[i].second.size();j++){
        cout<<setw(6)<<pgl[i].second[j];}
        cout<<"    |"<<pgl[i].first<<endl;} 
        
 mv=0;
 mimo=0;//и так понятно что обозначает)
for(i=0;i<pgl.size();i++){
mvv=0;
 for (k=i;k<pgl.size();k++){
    for(j=0;j<pgl[i].second.size();j++){
         if (pgl[i].second[j]<pgl[k].second[j]) {mimo++;}
         }
    if (mimo>0) mvv++;}    
    if (mvv>mv) mv=mvv;}
cout<<endl<<mv; 
  
//////////////////////////////////////////////////////////////////////////////////    
char src[50];
char dest[50];
cout<<endl<<"U+FDD0";
cout<<endl;
strcpy(src,"Нажмите любую клавишу, чтобы продолжить или любую другую, чтобы выйти.");
CharToOem(src,dest);
printf(dest);
 
 getch();   
  return 0;}
Добавлено через 2 часа 29 минут
пожалуйста,ну помогите бедному студенту, я сдал программирование на 5 ,преподаватель не поставит её пока я не сдам эту программу в 3 реализациях.. у меня стипендия накроется тогда..
Yandex
Объявления
23.01.2011, 19:00     Динамическое программирование. Вложенные коробки.
Ответ Создать тему
Опции темы

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