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

Динамическое программирование. Рыцарь. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
tymrfik
 Аватар для tymrfik
2 / 2 / 0
Регистрация: 27.12.2010
Сообщений: 89
28.12.2010, 16:33     Динамическое программирование. Рыцарь. #1
Необходимо написать три версии алгоритма для решения предложенной задачи.
• неэффективная, при помоши рекуррентного спуска.
• с использованием динамического программирования.
• модификация первой, основанная на механизме «запоминания».
Задание:
За долгую и верную службу Рыцарю позволено набрать сокровищ в сокровищнице своего сеньора. Сокровищница имеет форму прямоугольника, состоящего из отдельных "клеток" — прямоугольных комнат. В каждой комнате хранятся сокровища известной стоимости. Рыцарь может вынести сколько угодно сокровищ, но пройдя через сокровищницу только один раз. Он может начать с любой комнаты вдоль внешней северной стены сокровищницы (выбор комнаты — за рыцарем). На каждом шаге он может переходить в одну из трех "южно-соседних" комнат: южную, юго-восточную или юго-западную. Из комнат, граничащих с восточной или западной внешней стеной, возможны только два направления выхода. Закончить путь Рыцарь должен в любой из комнат на южной внешней стороне сокровищницы.
У Рыцаря есть план сокровищницы — прямоугольная таблица, в которой обозначены стоимости сокровищ каждой комнаты. Направлению с севера на юг соответствует направление сверху вниз на карте.
По заданной карте нужно найти один из допустимых путей, обеспечивающих наибольшую возможную сумму сокровищ.

Вход. Первая строка в тексте содержит два числа N и М, обозначающие "ширину" и "высоту", далее М строк по N неотрицательных целых чисел в каждой — стоимости сокровищ соответствующих комнат. Размеры сокровищницы не более чем 80x80 комнат.
Выход. В первой строке указывается номер (по порядку с запада на восток) комнаты северного ряда, из которой нужно начать движение, во второй — строка символов, означающих на¬правление очередного перехода (S — на юг, Е — на юго-восток, W — на юго-запад); в третьей — полученная максимально возможная суммарная стоимость. Если есть несколько путей с максимальной суммой, вывести любой из них.
Помогите хотя б советом.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.12.2010, 16:33     Динамическое программирование. Рыцарь.
Посмотрите здесь:

C++ Динамическое программирование
C++ Динамическое программирование
C++ динамическое программирование
Динамическое программирование. C++
C++ Динамическое программирование
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2010, 17:03     Динамическое программирование. Рыцарь. #2
tymrfik, вижу решение только с помощью ДП. Пойдет?
tymrfik
 Аватар для tymrfik
2 / 2 / 0
Регистрация: 27.12.2010
Сообщений: 89
28.12.2010, 17:13  [ТС]     Динамическое программирование. Рыцарь. #3
да, пойдет.!)
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2010, 17:34     Динамическое программирование. Рыцарь. #4
Создаете два массива a[M][N] и b[M][N], в оба сразу записываете входные данные.
Далее с массивом b[][] выполняете следующее:
C++
1
2
3
4
5
6
7
8
9
10
for(int i=M-2; i>=0; i--)
    for(j=0; j<N; j++)
    {
        int max=b[i-1][j];
        if(j>0 && b[i-1][j-1]>max)
            max=b[i-1][j-1];
        if(j<N-1 && b[i-1][j+1]>max)
            max=b[i-1][j+1];
        b[i][j]+=max;
    }
Далее находите максимум в нулевой строке массива b[][], это и будет ответ (максимально набранное сокровище).
Как выходные данные вывести подсказать (имея в запасе начальный массив a[][])?
tymrfik
 Аватар для tymrfik
2 / 2 / 0
Регистрация: 27.12.2010
Сообщений: 89
28.12.2010, 18:06  [ТС]     Динамическое программирование. Рыцарь. #5
Ага!! Больше спасибо!) И буду благодарен за подсказку про вывод, чтоб точно не вылететь.!!!!
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
29.12.2010, 02:48     Динамическое программирование. Рыцарь. #6
Сообщение было отмечено автором темы, экспертом или модератором как ответ
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
#include<iostream>
#include<stdio.h>
#include<conio.h>
using namespace std;
int main()
{
    int N, M, i, j, i_temp, **a, **b, sum;
    cin>>N>>M;
    a=new int*[M];
    b=new int*[M];
    for(i=0; i<M; i++)
    {
        a[i]=new int[N];
        b[i]=new int[N];
        for(j=0; j<N; j++)
        {
            cin>>a[i][j];
            b[i][j]=a[i][j];
        }
    }
    for(i=M-2; i>=0; i--)
        for(j=0; j<N; j++)
        {
                int max=b[i+1][j];
                if(j>0 && b[i+1][j-1]>max)
                        max=b[i+1][j-1];
                if(j<N-1 && b[i+1][j+1]>max)
                        max=b[i+1][j+1];
                b[i][j]+=max;
        }
    i_temp=0;
    for(i=1; i<N; i++)
        if(b[0][i]>b[0][i_temp])
            i_temp=i;
    sum=b[0][i_temp];
    cout<<i_temp+1<<endl;// выводим номер комнаты, учитывая что номера комнат начинаются с 1
    for(i=1; i<M; i++)
    {
        if(b[i-1][i_temp]-a[i-1][i_temp]==b[i][i_temp])
            cout<<"S";
        else
            if(i_temp>0 && b[i-1][i_temp]-a[i-1][i_temp]==b[i][i_temp-1])
            {
                cout<<"W";
                i_temp--;
            }
            else
            {
                cout<<"E";
                i_temp++;
            }
    }
    cout<<endl<<sum;
    return 0;
    }
tymrfik
 Аватар для tymrfik
2 / 2 / 0
Регистрация: 27.12.2010
Сообщений: 89
29.12.2010, 17:13  [ТС]     Динамическое программирование. Рыцарь. #7
Спасибо!!! Оч помогает. Можно еще узнать на счет варианта с модиф. рекурсией?=)
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
29.12.2010, 20:06     Динамическое программирование. Рыцарь. #8
Цитата Сообщение от tymrfik Посмотреть сообщение
Можно еще узнать на счет варианта с модиф. рекурсией?=)
Неэффективные алгоритмы - это не ко мне.
tymrfik
 Аватар для tymrfik
2 / 2 / 0
Регистрация: 27.12.2010
Сообщений: 89
16.01.2011, 15:57  [ТС]     Динамическое программирование. Рыцарь. #9
Эт точно очень неэффективные алгоритмы + громоздкие они походу получаются (по крайней мере у меня точно). А могли бы подсказать еще немного: вот 3 вариант - " модификация первой, основанная на механизме «запоминания»." - будет программа с мемоизацией - это запоминание промежуточных результатов работы рекурентного алгоритма. Только вот интересный факт, в своем рекурентном коде не представляю, где нужно вставить эту мемоизацию. + где я не искал, везде только мемоизация встречается с Java языком?!!!
#include <iostream>
#include <math.h>

using std::cout;
using std::cin;
using std::endl;

struct coords
{
int x,y;
coords(int p_x=0, int p_y=0): x(p_x), y(p_y) {}
};

class Stack
{
private:
coords array[1024]; // Чтоб не мучаться с дин. массивом
int index;
public:
Stack(): index(0) {}
void push(const coords& obj)
{
if (index<=1024) array[index++]=obj;
}
coords pop() {if (index-1>=0) --index;}
Stack& operator=(const Stack& obj)
{
index=obj.index;
for (int i=0; i<index; ++i) array[i]=obj.array[i];
}
void Print()
{
for (int i=0; i<index; ++i) std::cout<<"x="<<array[i].x<<", y="<<array[i].y<<std::endl;
}
};


const int n=4;
const int m=5;

int matrix[n][m];
void Getmatr (int, int); //матрица из случайных чисел
void Myprint (int, int); //выводит матрицу
void find(bool**, int&, int, int, int, Stack&, Stack&);

int main()
{
int sum=0;
bool **field; //двумерное "поле"
field =new bool*[n];
for (int i=0; i<n; i++)
{
field[i]=new bool[m];
for (int j=0; j<n; j++) field[i][j]=false; // Первоначально никакую клетку не посетили
}
Getmatr(n,m);
Stack c;
for (int i=0; i<m; i++) // Проходим по элементам первой строки
{
int temp_sum=0;
Stack a,b;
find(field,temp_sum,0,i,0,a,b);
if (temp_sum>sum)
{
sum=temp_sum;
c=a;
}
}
Myprint(n,m);
cout<<"Max: "<<sum<<endl;
c.Print();
int a;
cin>>a;
for (int i=0; i<n; i++)
delete []field[i];
delete []field;
return 0;
}

void Getmatr (int n, int m)
{
int RANGE_MIN=0;
int RANGE_MAX=10;
srand((unsigned)time(NULL));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
matrix[i][j]=
static_cast<int>(((double)rand()/(double) RAND_MAX) * RANGE_MAX + RANGE_MIN);
}
}

void Myprint (int n, int m)
{
for(int i=0;i<n;i++)
{
cout<<endl;
for(int j=0;j<m;j++)
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}

void find(bool **field, int& sum, int i, int j, int s, Stack& primary, Stack& current)
{
if (i<0 || i>=n || j<0 || j>=m)
return;
if (i==n-1)
{
if (s+matrix[i][j]>sum)
{
sum=s+matrix[i][j];
primary=current;
primary.push(coords(j,i));
}
return;
}
if (!field[i][j])
{
field[i][j]=true;
current.push(coords(j,i));
int temp=s+matrix[i][j];
find(field,sum,i+1,j,temp,primary,current);
find(field,sum,i+1,j-1,temp,primary,current);
find(field,sum,i+1,j+1,temp,primary,current);
current.pop();
field[i][j]=false;
}
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.01.2011, 17:48     Динамическое программирование. Рыцарь. #10
tymrfik, Я представляю себе это например так:
- завести структуру для описания комнаты, в нее должен быть включен например вектор (для хранения всех возможных результатов для этой комнаты).
- создать матрицу размером как сокровищница, для хранения элементов типа структуры комнаты.
- для верхнего ряда в каждом векторе каждой структуры будет только одно значение.
- проходим верхний ряд заполняя векторы структур второго ряда (учитывая кол-во и значения векторов верхнего ряда). После такого прохождения у всех векторов второго ряда получится три значения, за исключением векторов, граничащих с левой или правой стен (у них по два значения)
- и т.д. проходим очередной ряд заполняя векторы структур следующего ряда (учитывая кол-во и значения векторов очередного ряда).
tymrfik
 Аватар для tymrfik
2 / 2 / 0
Регистрация: 27.12.2010
Сообщений: 89
16.01.2011, 18:55  [ТС]     Динамическое программирование. Рыцарь. #11
Вроде этого?
#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

const int n=4;
const int m=5;
int matrix[n][m];

void Getmatr (int, int); //ìàòðèöà èç ñëó÷àéíûõ ÷èñåë
void Myprint (int, int); //âûâîäèò ìàòðèöó
void find(bool**, int&, int, int, int);

int main()
{
int sum=0;
bool **field; //äâóìåðíîå "ïîëå"
field =new bool*[n];
for (int i=0; i<n; i++)
{
field[i]=new bool[m];
for (int j=0; j<n; j++) field[i][j]=false; // Ïåðâîíà÷àëüíî íèêàêóþ êëåòêó íå ïîñåòèëè
}
Getmatr(n,m);
for (int i=0; i<m; i++) // Ïðîõîäèì ïî ýëåìåíòàì ïåðâîé ñòðîêè
{
int temp_sum=0;
find(field,temp_sum,0,i,0);
if (temp_sum>sum) sum=temp_sum;
}
Myprint(n,m);
cout<<"Max: "<<sum<<endl;
int a;
cin>>a;
for (int i=0; i<n; i++)
delete []field[i];
delete []field;
return 0;
}
void Getmatr (int n, int m)
{
int RANGE_MIN=0;
int RANGE_MAX=10;
srand((unsigned)time(NULL));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
matrix[i][j]=
static_cast<int>(((double)rand()/(double) RAND_MAX) * RANGE_MAX + RANGE_MIN);
}
}
void Myprint (int n, int m)
{
for(int i=0;i<n;i++)
{
cout<<endl;
for(int j=0;j<m;j++)
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}
void find(bool **field, int& sum, int i, int j, int s)
{
if (i<0 || i>=n || j<0 || j>=m)
return;
if (i==n-1)
{
if (s+matrix[i][j]>sum) sum=s+matrix[i][j];
return;
}
if (!field[i][j])
{
field[i][j]=true;
int temp=s+matrix[i][j];
find(field,sum,i+1,j,temp);
find(field,sum,i+1,j-1,temp);
find(field,sum,i+1,j+1,temp);
field[i][j]=false;
}
}

Добавлено через 5 минут
#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

const int n=4;
const int m=5;
int matrix[n][m];

void Getmatr (int, int); //ìàòðèöà èç ñëó÷àéíûõ ÷èñåë
void Myprint (int, int); //âûâîäèò ìàòðèöó
void find(bool**, int&, int, int, int);

int main()
{
int sum=0;
bool **field; //äâóìåðíîå "ïîëå"
field =new bool*[n];
for (int i=0; i<n; i++)
{
field[i]=new bool[m];
for (int j=0; j<n; j++) field[i][j]=false; // Ïåðâîíà÷àëüíî íèêàêóþ êëåòêó íå ïîñåòèëè
}
Getmatr(n,m);
for (int i=0; i<m; i++) // Ïðîõîäèì ïî ýëåìåíòàì ïåðâîé ñòðîêè
{
int temp_sum=0;
find(field,temp_sum,0,i,0);
if (temp_sum>sum) sum=temp_sum;
}
Myprint(n,m);
cout<<"Max: "<<sum<<endl;
int a;
cin>>a;
for (int i=0; i<n; i++)
delete []field[i];
delete []field;
return 0;
}
void Getmatr (int n, int m)
{
int RANGE_MIN=0;
int RANGE_MAX=10;
srand((unsigned)time(NULL));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
matrix[i][j]=
static_cast<int>(((double)rand()/(double) RAND_MAX) * RANGE_MAX + RANGE_MIN);
}
}
void Myprint (int n, int m)
{
for(int i=0;i<n;i++)
{
cout<<endl;
for(int j=0;j<m;j++)
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}
void find(bool **field, int& sum, int i, int j, int s)
{
if (i<0 || i>=n || j<0 || j>=m)
return;
if (i==n-1)
{
if (s+matrix[i][j]>sum) sum=s+matrix[i][j];
return;
}
if (!field[i][j])
{
field[i][j]=true;
int temp=s+matrix[i][j];
find(field,sum,i+1,j,temp);
find(field,sum,i+1,j-1,temp);
find(field,sum,i+1,j+1,temp);
field[i][j]=false;
}
}

Добавлено через 12 минут
Вроде этого?
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
#include <iostream>
#include <math.h>
#include <vector>
 
using namespace std;
 
const int n=4;
const int m=5;
int matrix[n][m];
 
void Getmatr (int, int);  //Г¬Г*òðèöГ* ГЁГ§ ñëó÷Г*Г©Г*ûõ Г·ГЁГ±ГҐГ«
void Myprint (int, int);  //âûâîäèò Г¬Г*òðèöó
void find(bool**, int&, int, int, int);
 
int main()
{
    int sum=0;
    bool **field;  //äâóìåðГ*îå "ïîëå"
    field =new bool*[n];
    for (int i=0; i<n; i++)
    {
        field[i]=new bool[m];
        for (int j=0; j<n; j++) field[i][j]=false;    // ÏåðâîГ*Г*Г·Г*ëüГ*Г® Г*ГЁГЄГ*ГЄГіГѕ êëåòêó Г*ГҐ ïîñåòèëè
    }
    Getmatr(n,m);    
    for (int i=0; i<m; i++)           // Ïðîõîäèì ГЇГ® ýëåìåГ*ГІГ*Г¬ ïåðâîé ñòðîêè
    {
        int temp_sum=0;
        find(field,temp_sum,0,i,0);
        if (temp_sum>sum) sum=temp_sum;
    }
    Myprint(n,m);
    cout<<"Max: "<<sum<<endl;
    int a;
    cin>>a;
    for (int i=0; i<n; i++)
        delete []field[i];
    delete []field;
    return 0;
}
void Getmatr (int n, int m)
{
       int RANGE_MIN=0;
       int RANGE_MAX=10;
       srand((unsigned)time(NULL));
       for(int i=0;i<n;i++)
       {
           for(int j=0;j<m;j++)
           matrix[i][j]=
            static_cast<int>(((double)rand()/(double) RAND_MAX) * RANGE_MAX + RANGE_MIN);
       }
}
void Myprint (int n, int m)
{
    for(int i=0;i<n;i++)
    {  
        cout<<endl;
        for(int j=0;j<m;j++)
            cout<<matrix[i][j]<<" ";
    }
    cout<<endl;
}
void find(bool **field, int& sum, int i, int j, int s)
{
    if (i<0 || i>=n || j<0 || j>=m) 
        return;
    if (i==n-1)
    {
        if (s+matrix[i][j]>sum) sum=s+matrix[i][j];
        return;
    }
    if (!field[i][j])
    {
        field[i][j]=true;
        int temp=s+matrix[i][j];       
        find(field,sum,i+1,j,temp);
        find(field,sum,i+1,j-1,temp);
        find(field,sum,i+1,j+1,temp);
        field[i][j]=false;
    }
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.01.2011, 18:59     Динамическое программирование. Рыцарь. #12
Вроде этого?
Если вопрос ко мне, то я не это имел ввиду.
tymrfik
 Аватар для tymrfik
2 / 2 / 0
Регистрация: 27.12.2010
Сообщений: 89
17.01.2011, 08:28  [ТС]     Динамическое программирование. Рыцарь. #13
А вы могли бы подсказать псевдокод по С++, когда уже выполняются такие шаги:
Цитата Сообщение от valeriikozlov Посмотреть сообщение
tymrfik, Я представляю себе это например так:
....
- проходим верхний ряд заполняя векторы структур второго ряда (учитывая кол-во и значения векторов верхнего ряда). После такого прохождения у всех векторов второго ряда получится три значения, за исключением векторов, граничащих с левой или правой стен (у них по два значения)
- и т.д. проходим очередной ряд заполняя векторы структур следующего ряда (учитывая кол-во и значения векторов очередного ряда).
Примерно так:
[C++] ...
for(j=0;j<N;i++)
mas[1][j]=random b[k]; /*b[k] - структура, которая хранит значения для комнаты, в данном варианте одномерный массив.*/
for (i=1;i<M;i++)
mas[i][j]=?[/C++]
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
17.01.2011, 09:37     Динамическое программирование. Рыцарь. #14
Примерно так:
[C++] ...
for(j=0;j<N;i++)
mas[1][j]=random b[k]; /*b[k] - структура, которая хранит значения для комнаты, в данном варианте одномерный массив.*/
for (i=1;i<M;i++)
mas[i][j]=?[/C++]
Нет, не так:
Допустим массив со значениями комнат: matrix[n][m]
Структура, со значения комнат такая:
struct room{
vector<int> v;
};
Создаем массив:
room field[n][m];
Далее запоняем первую строку field[][]:
for(int i=0; i<m; i++)
field[0][i]->v.push_back(matrix[0][j]);
Далее так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i=0; i<n-1; i++)
    for(int j=0; j<m; j++)
    {  
        vector<int>::iterator y;
        for(y=mas[i][j]->v.begin(); y!=mas[i][j]->v.end(); ++y)
        {
             mas[i+1][j]->v.push_back(matrix[i+1][j]+*y);
             if(j>0)
                mas[i+1][j-1]->v.push_back(matrix[i+1][j-1]+*y);
            if(j<m-1)
                mas[i+1][j+1]->v.push_back(matrix[i+1][j+1]+*y);
       }
   }
После этого в последней строке массива mas[n-1][i], в каждом элементе в векторе v будут находится все возможные значения набранных сумм.
Перебирайте их, находите максимальное значение.
tymrfik
 Аватар для tymrfik
2 / 2 / 0
Регистрация: 27.12.2010
Сообщений: 89
26.01.2011, 17:02  [ТС]     Динамическое программирование. Рыцарь. #15
Вот еще одна моя попытка решить эту задачу по-другому через рекурсию, сам пока доступным для зачета. Псевдокод для самой рекурсивной функции:
[C++]int rec(int i,int j){
if(i==n-1) return m[i][j];
if(j==0) {s1 и s3}
if(j==m-1) {s1 и s2}
s1=m[i][j]+rec(i+1,j-1);
s2=m[i][j]+rec(i+1,j);
s3=m[i][j]+rec(i+1,j+1);
return(max(s1,s2,s3));[/C++]
Подскажите как быть с самыми первыми ячейками [0][0], [0][1], .....[0][m-1]?!!!!! их нужно сначала перебирать через цикл и считать для них сумму?!!!! Помогите с кодом!!!! (До утра успеть бы.)
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
26.01.2011, 18:40     Динамическое программирование. Рыцарь. #16
Цитата Сообщение от tymrfik Посмотреть сообщение
модификация первой, основанная на механизме «запоминания».
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
#include<iostream>
#include<vector>
#include<stdio.h>
#include<conio.h>
using namespace std;
    struct room{
        vector<int> v;
    };
 
int main()
{
    vector<int>::iterator y;
    room **field;
    char *mas_res;
    int N, M, i, j,  **matrix, sum=0, i_res=0, i_sum=0, num, Sum;
    cin>>N>>M;
    mas_res=new char[M-1];
    field=new room*[M];
    matrix=new int*[M];
    for(i=0; i<M; i++)
    {
        field[i]=new room[N];
        matrix[i]=new int[N];
        for(j=0; j<N; j++)
            cin>>matrix[i][j];    
    }
    for(int i=0; i<N; i++)
        field[0][i].v.push_back(matrix[0][i]);
    for(int i=0; i<M-1; i++)
    for(int j=0; j<N; j++)
    {  
          for(y=field[i][j].v.begin(); y!=field[i][j].v.end(); ++y)
        {
             field[i+1][j].v.push_back(matrix[i+1][j]+*y);
             if(j>0)
                field[i+1][j-1].v.push_back(matrix[i+1][j-1]+*y);
            if(j<N-1)
                field[i+1][j+1].v.push_back(matrix[i+1][j+1]+*y);
        }
    }
    for(i=0; i<N; i++)
        for(y=field[M-1][i].v.begin(); y!=field[M-1][i].v.end(); ++y)
            if(sum<*y)
            {
                sum=*y;
                i_sum=i;
            }
    Sum=sum;
    for(i=M-2; i>=0; i--)
    {
        bool fl=true;
        for(y=field[i][i_sum].v.begin(); y!=field[i][i_sum].v.end(); ++y)
            if(sum-matrix[i+1][i_sum]==*y)
            {
                sum=*y;
                fl=false;
                mas_res[i_res++]='S';
                break;
            }
        if(fl && i_sum>0)
        {
            for(y=field[i][i_sum-1].v.begin(); y!=field[i][i_sum-1].v.end(); ++y)
                if(sum-matrix[i+1][i_sum]==*y)
                {
                    sum=*y;
                    i_sum--;
                    fl=false;               
                    mas_res[i_res++]='E';
                    break;
                }
        }
        if(fl && i_sum<N-1)
        {
            for(y=field[i][i_sum+1].v.begin(); y!=field[i][i_sum+1].v.end(); ++y)
                if(sum-matrix[i+1][i_sum]==*y)
                {
                    sum=*y;
                    i_sum++;
                    fl=false;       
                    mas_res[i_res++]='W';       
                    break;                  
                }
        }
    }
    cout<<i_sum+1<<endl;
    for(i=M-2; i>=0; i--)
        cout<<mas_res[i];
    cout<<endl<<Sum<<endl;
    return 0;
        }
Два важных момента:
- я как всегда не освободил память, выделенную динамически. Хоть как-то свою лепту внесете.
- потестируйте код. Если что не устроит пишите, но сегодня буду недоступен, постараюсь завтра утром посмотреть (сам проверил, но немного).
tymrfik
 Аватар для tymrfik
2 / 2 / 0
Регистрация: 27.12.2010
Сообщений: 89
27.01.2011, 09:04  [ТС]     Динамическое программирование. Рыцарь. #17
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
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <stdio.h>
using namespace std;
 
 
int maxim(int s1,int s2,int s3)
 {
  int max=s1;
  if(max<s2) max=s2;
  if(max<s3) max=s3;
  cout<<max;
 }
int rec(int i, int j)
{
      int n=2;
      int m=3;
      int s1,s2,s3;
    int **a = new int *[n];
   for (i = 0; i < n; i++) 
   {
    a[i] = new int [m];
    } 
    if(i==n-1)return a[i][j];
    if(j==0) {return maxim(s1,0,s3);}
    if(j==m-1){return maxim(s1,s2,0);}
    s1=a[i][j]+rec(i+1,j-1);
    s2=a[i][j]+rec(i+1,j);
    s3=a[i][j]+rec(i+1,j+1);
    return(maxim(s1,s2,s3));
    for (i = 0; i < n; i++) {
  delete []a[i];
}
delete []a;
}
int main(int argc, char * argv[])
{
 int s1,s2,s3;
 int n = 0;
 int m = 0;
 
 int **a;
 
 //îòêðûâГ*ГҐГ¬ ГґГ*éë
 FILE * fp = fopen("test.txt", "r");
 if (fp)
 {
  //Г·ГЁГІГ*ГҐГ¬ êîëè÷åñòâî ñòðîê ГЁ ñòîëáöîâ
  fscanf(fp, "%d %d", &n, &m);
 
  //âûäåëÿåì ìåñòî
  *a = new int(n);
  for (int i = 0; i < n; i++) a[i] = new int(m);
 
  //ñ÷èòûâГ*ГҐГ¬ Г¤Г*Г*Г*ûå ГЁГ§ ГґГ*éëГ* Гў Г¬Г*òðèöó
  for (int i = 0; i < n; i++)
  {
   for (int j = 0; j < m; j++)
   {
    fscanf(fp, "%d", &a[i][j]);
   }
  }
  
  //Г§Г*êðûâГ*ГҐГ¬ ГґГ*éë
  fclose(fp);
 }
 
 //ГЇГҐГ·Г*ГІГј Г¬Г*òðèöû
 for (int i = 0; i < n; i++)
 {
  for (int j = 0; j < m; j++)
  {
   printf("%d ", a[i][j]);
  }
 
  printf("\n");
 }
  for (int j = 0; j < m; j++)
    {    
      cout<<maxim(s1,s2,s3);
    }
 
 //îñâîáîæäåГ*ГЁГҐ ГЇГ*ìÿòè
/*for (int i = 0; i < n; i++) delete a[i];
 delete *a;*/
 
system("PAUSE");
    return EXIT_SUCCESS;
}
Можно ли как-нибудь исправить "это"?! "жуткое зрелище здесь"
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
27.01.2011, 09:29     Динамическое программирование. Рыцарь. #18
tymrfik, А что имено исправить? (см комментарии):
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
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <stdio.h>
using namespace std;
 
 
int maxim(int s1,int s2,int s3)// функция объявлена как возвращающая значение типа int , на самом деле ничего не возвращает
 {
  int max=s1;
  if(max<s2) max=s2;
  if(max<s3) max=s3;
  cout<<max;
 }
int rec(int i, int j)// тоже непонятная функция, при каждом ее вызове создается матрица a[2][3] 
{
      int n=2;
      int m=3;
      int s1,s2,s3;
    int **a = new int *[n];
   for (i = 0; i < n; i++) 
   {
    a[i] = new int [m];
    } 
    if(i==n-1)return a[i][j];
    if(j==0) {return maxim(s1,0,s3);}// значения переменным s1,s2,s3 нигде не определяются, но используются в вызове функции maxim() 
    if(j==m-1){return maxim(s1,s2,0);}
    s1=a[i][j]+rec(i+1,j-1);
    s2=a[i][j]+rec(i+1,j);
    s3=a[i][j]+rec(i+1,j+1);
    return(maxim(s1,s2,s3));
    for (i = 0; i < n; i++) {
  delete []a[i];
}
delete []a;
}
int main(int argc, char * argv[])
{
 int s1,s2,s3;
 int n = 0;
 int m = 0;
 
 int **a;
 
 //открываем файл
 FILE * fp = fopen("test.txt", "r");
 if (fp)
 {
  //читаем количество строк и столбцов
  fscanf(fp, "%d %d", &n, &m);
 
  //выделяем место
  *a = new int(n);
  for (int i = 0; i < n; i++) a[i] = new int(m);
 
  //считываем данные из файла в матрицу
  for (int i = 0; i < n; i++)
  {
   for (int j = 0; j < m; j++)
   {
    fscanf(fp, "%d", &a[i][j]);
   }
  }
  
  //закрываем файл
  fclose(fp);
 }
 
 //печать матрицы
 for (int i = 0; i < n; i++)
 {
  for (int j = 0; j < m; j++)
  {
   printf("%d ", a[i][j]);
  }
 
  printf("\n");
 }
  for (int j = 0; j < m; j++)
    {    
      cout<<maxim(s1,s2,s3);// значения переменным s1,s2,s3 нигде не определяются, но используются в вызове функции maxim() 
    }
 
 //освобождение памяти
/*for (int i = 0; i < n; i++) delete a[i];
 delete *a;*/
 
system("PAUSE");
    return EXIT_SUCCESS;
}//вызова функции rec() вообще нет
Если честно, то мне не понятна задумка автора.
tymrfik
 Аватар для tymrfik
2 / 2 / 0
Регистрация: 27.12.2010
Сообщений: 89
27.01.2011, 10:00  [ТС]     Динамическое программирование. Рыцарь. #19
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
using namespace std;
 
const int n=2;
const int m=3;
int a[n][m];
 
int maxim(int a,int b,int c, int max)
 {
   max=a;
  if(max<b) max=b;
  if(max<c) max=c;
  return max;
 }
int rec(int i, int j)
{
    int s1,s2,s3,sum;
    if(i==n-1)return a[i][j];
    if(j==0) 
    {
      s1=a[i][j]+rec(i+1,j-1);
      s3=a[i][j]+rec(i+1,j+1);
    }
    if(j==m-1)
    {  
     s1=a[i][j]+rec(i+1,j-1);
     s2=a[i][j]+rec(i+1,j);
    }
    s1=a[i][j]+rec(i+1,j-1);
    s2=a[i][j]+rec(i+1,j);
    s3=a[i][j]+rec(i+1,j+1);
    return(maxim(s1,s2,s3,sum));
}
Эту часть вроде исправили. А как верно вызвать функцию rec в main? еще учесть элементы первой строки нужно.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.01.2011, 11:46     Динамическое программирование. Рыцарь.
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
27.01.2011, 11:46     Динамическое программирование. Рыцарь. #20
tymrfik, Это вообще какой вариант? Этот?:
Цитата Сообщение от tymrfik Посмотреть сообщение
• неэффективная, при помоши рекуррентного спуска.
Цитата Сообщение от tymrfik Посмотреть сообщение
Эту часть вроде исправили.
Эту часть довели до рабочего состояния (почти).
Почему массив a[2][3]? Это размер сокровищницы такой? Сам путь в сокровищнице вообще не отслеживается.
Мне легче написать свой вариант. Только напишите, какой именно вариант нужен.
Yandex
Объявления
27.01.2011, 11:46     Динамическое программирование. Рыцарь.
Ответ Создать тему
Опции темы

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