Форум программистов, компьютерный форум 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
 Аватар для opax
0 / 0 / 0
Регистрация: 29.03.2010
Сообщений: 21
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 реализациях.. у меня стипендия накроется тогда..
 
Текущее время: 23:19. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru