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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
tymrfik
2 / 2 / 0
Регистрация: 27.12.2010
Сообщений: 89
#1

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

28.12.2010, 16:33. Просмотров 1216. Ответов 19
Метки нет (Все метки)

Необходимо написать три версии алгоритма для решения предложенной задачи.
• неэффективная, при помоши рекуррентного спуска.
• с использованием динамического программирования.
• модификация первой, основанная на механизме «запоминания».
Задание:
За долгую и верную службу Рыцарю позволено набрать сокровищ в сокровищнице своего сеньора. Сокровищница имеет форму прямоугольника, состоящего из отдельных "клеток" — прямоугольных комнат. В каждой комнате хранятся сокровища известной стоимости. Рыцарь может вынести сколько угодно сокровищ, но пройдя через сокровищницу только один раз. Он может начать с любой комнаты вдоль внешней северной стены сокровищницы (выбор комнаты — за рыцарем). На каждом шаге он может переходить в одну из трех "южно-соседних" комнат: южную, юго-восточную или юго-западную. Из комнат, граничащих с восточной или западной внешней стеной, возможны только два направления выхода. Закончить путь Рыцарь должен в любой из комнат на южной внешней стороне сокровищницы.
У Рыцаря есть план сокровищницы — прямоугольная таблица, в которой обозначены стоимости сокровищ каждой комнаты. Направлению с севера на юг соответствует направление сверху вниз на карте.
По заданной карте нужно найти один из допустимых путей, обеспечивающих наибольшую возможную сумму сокровищ.

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

Динамическое программирование! - C++
#include <cstdio> #include <algorithm> using namespace std; int a, n, m; int main() { scanf(" %d %d", &n,...

Динамическое программирование - C++
Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт У Пети есть полоска бумаги, разделенная на N клеток. Он хочет...

Динамическое программирование - C++
Усложнили задачу мне.... : Дан массив A. Необходимо найти максимальную сумму элементов прямоугольного подмассива по всем возможным...

ДП Динамическое программирование - C++
ограничение времени на тест: 0.5 сек. ограничение памяти на тест: 65536 KB. Рассмотрим все строки длины N, состоящие только из букв...

Динамическое программирование. - C++
Помогите, пожалуйста, составить алгоритм по одному из ниже представленных заданий, используя методы динамического программирования и жадных...

Динамическое программирование - C++
Подскажите что не так в решении. #include <iostream> #include <stdio.h> using namespace std; const int N = 5001; int...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2010, 17:03 #2
tymrfik, вижу решение только с помощью ДП. Пойдет?
tymrfik
2 / 2 / 0
Регистрация: 27.12.2010
Сообщений: 89
28.12.2010, 17:13  [ТС] #3
да, пойдет.!)
valeriikozlov
Эксперт C++
4670 / 2496 / 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
2 / 2 / 0
Регистрация: 27.12.2010
Сообщений: 89
28.12.2010, 18:06  [ТС] #5
Ага!! Больше спасибо!) И буду благодарен за подсказку про вывод, чтоб точно не вылететь.!!!!
valeriikozlov
Эксперт C++
4670 / 2496 / 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
2 / 2 / 0
Регистрация: 27.12.2010
Сообщений: 89
29.12.2010, 17:13  [ТС] #7
Спасибо!!! Оч помогает. Можно еще узнать на счет варианта с модиф. рекурсией?=)
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
29.12.2010, 20:06 #8
Цитата Сообщение от 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++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.01.2011, 17:48 #10
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++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.01.2011, 18:59 #12
Вроде этого?
Если вопрос ко мне, то я не это имел ввиду.
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++
4670 / 2496 / 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
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]?!!!!! их нужно сначала перебирать через цикл и считать для них сумму?!!!! Помогите с кодом!!!! (До утра успеть бы.)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.01.2011, 17:02
Привет! Вот еще темы с ответами:

Динамическое программирование - C++
Помогите решить задачу! Я что-то особо не соображу... 1.Написать программу, реализующую действия: а. сформировать ленточную матрицу...

Динамическое программирование - C++
Мячик прыгает по лестнице, состоящей из N ступенек, строго сверху вниз. За один прыжок он может отпрыгнуть на не более M ступенек....

Динамическое программирование - C++
Столкнулся с такой задачей. Есть 6 фигурок площадью 3. Нужно узнать, сколькими способами можно полностью замостить ими поле n на m,...

Динамическое программирование - C++
Помогите пожалуйста,кто может, со следующими задачами, так как в С++ слабо разбираюсь, а к понедельнику надо сдать... 1. Определить...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
26.01.2011, 17:02
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru