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

@opax · Регистрация: 29.03.2010

Студворк — интернет-сервис помощи студентам

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

Задача:
Даны 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 минуты
пожалуйста,помогите..

@Merlin666 · 16.01.2011, 21:51

Вам понадобится метод анализа для данной коробки, помещается ли другая в нее..статический..что-то нечто:

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 · 16.01.2011, 22:03 **[ТС]**

спасибо, а посоветуйте как лучше хранить размеры коробок, номера и объемы.. чтобы динамически.. многомерные векторы?

@Merlin666 · 16.01.2011, 22:16

Чтобы динамически-отличный выбор односвязный циклический или нециклический список..)

@opax · 16.01.2011, 22:22 **[ТС]**

не могли бы вы накидать динамический способ реализации ?.. остальные попробую сам сделать..

@Merlin666 · 16.01.2011, 22:24

Посмотрите тут http://www.dmtsoft.ru/bn/373/as/oneaticleshablon/
Просто нет компилятора под рукой=( в голове обрабатываю..)

valeriikozlov · 17.01.2011, 09:08

Сообщение от 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 · 17.01.2011, 09:35 **[ТС]**

Спасибо огромное!

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

Прога не всегда работает правильно..

@opax · 23.01.2011, 19:00 **[ТС]**

Сообщение от 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 реализациях.. у меня стипендия накроется тогда..

Новые блоги и статьи Все статьи Все блоги /
Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .

@opax 0 / 0 / 1 Регистрация: 29.03.2010 Сообщений: 21

	Динамическое программирование. Вложенные коробки. 16.01.2011, 21:38. Показов 10916. Ответов 8 Метки нет (Все метки) Необходимо написать три версии алгоритма для решения предложенной задачи. • неэффективная, при помоши рекуррентного спуска. • с использованием динамического программирования. • модификация первой, основанная на механизме «мемоизации». Задача: Даны N коробок в форме прямоугольных параллелепипедов размерами aibici. Некоторые из них, как правило, можно вложить в другие. Толщина стенок коробок пренебрежимо мала, но строго больше нуля. Коробки разрешается вращать, но только на углы, кратные 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 минуты пожалуйста,помогите.. 0

@opax 0 / 0 / 1 Регистрация: 29.03.2010 Сообщений: 21
	16.01.2011, 22:03 [ТС]
	спасибо, а посоветуйте как лучше хранить размеры коробок, номера и объемы.. чтобы динамически.. многомерные векторы? 0

@Merlin666 98 / 98 / 29 Регистрация: 26.12.2010 Сообщений: 220
	16.01.2011, 22:16
	Чтобы динамически-отличный выбор односвязный циклический или нециклический список..) 0

@opax 0 / 0 / 1 Регистрация: 29.03.2010 Сообщений: 21
	16.01.2011, 22:22 [ТС]
	не могли бы вы накидать динамический способ реализации ?.. остальные попробую сам сделать.. 0

@Merlin666 98 / 98 / 29 Регистрация: 26.12.2010 Сообщений: 220
	16.01.2011, 22:24
	Посмотрите тут http://www.dmtsoft.ru/bn/373/as/oneaticleshablon/ Просто нет компилятора под рукой=( в голове обрабатываю..) 0

@opax 0 / 0 / 1 Регистрация: 29.03.2010 Сообщений: 21
	17.01.2011, 09:35 [ТС]
	Спасибо огромное! если не сложно могли бы это посмотреть.. там задание,псевдокод и мой код на с++... если в последовательности есть одинаковые элементы, программа неправильно работает... Прога не всегда работает правильно.. 0