VPF::Найти монеты - Форум программистов

almagnit

Дата 9.4.2008, 20:46 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 283
Регистрация: 3.4.2008

Репутация: нет
Всего: 7

Задача такая:

В матрице размером n на m находятся целые числа,

нужно передвигаясь в право и вниз (от левого верхнего угла к правому нижнему)

найти такой путь по которому можно было набрать максимальную сумму чисел матрицы.

Прошу подсказать тематику решения данной задачи.

Я делаю ее методом перебора всех возможных сумм в матрице, но если матрица хотябы 8х8 то поиск

слишком затягивается smile

Akina

Дата 9.4.2008, 20:56 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Обычная заливка.

--------------------

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

maxdiver

Дата 9.4.2008, 21:43 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18

almagnit
Простая динамика. Динамическое программирование.
Решение получится за O (размер карты).
Если хотите, могу выложить полное описание решения и код (сразу не выкладываю, вдруг вы хотите сам придумать smile

)

Akina
Какая заливка??

Это сообщение отредактировал(а) maxdiver - 9.4.2008, 21:44

almagnit

Дата 9.4.2008, 21:57 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 283
Регистрация: 3.4.2008

Репутация: нет
Всего: 7

maxdiver вылаживай !

Буду признателен

Akina

Дата 9.4.2008, 22:29 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Цитата(maxdiver @ 9.4.2008, 22:43

)

Какая заливка??

Заливка матрицы максимальными суммами... в каждую клетку можно попасть из 1 или из 2 других. Соответственно в каждую клетку, куда ведет 1 дорога, помещаем набранную по дороге туда сумму, а если 2 - то туда помещается максимальная из 2 сумм... топаем от начала, сперва заполняется одна горизонталь, потом вторая, потом третья... и так далее... О(1), все верно. Думаю, твой код делает именно это.

--------------------

almagnit

Дата 9.4.2008, 22:37 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 283
Регистрация: 3.4.2008

Репутация: нет
Всего: 7

В предложенном условии задача состоит в нахождении "максимальной суммы" клетки (n,m)

Я не нашел решения задачи в предложенном Вами алгоритме

P.S.
может плохо искал ?

maxdiver

Дата 9.4.2008, 22:42 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18

Akina
Да, по описанию абсолютно то же. Но название алгоритму ты дал довольно оригинальное smile

almagnit
Код и своё описание выложу завтра.

almagnit

Дата 10.4.2008, 01:29 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 283
Регистрация: 3.4.2008

Репутация: нет
Всего: 7

Akina

Прошу извинить меня за невнимательность.

Действительно плохо искал.

В соответсвии с описанным алгоритмом написал программу, все работает !

Для проверки можно вставить в Builder.

Akina, maxdiver - спасибо за вразумление smile

Код


#include <iostream.h>
#include <vcl.h>
#pragma hdrstop
#pragma argsused
int main(int argc, char* argv[])
{
  String s="";
  int n,m,i,j,s1,s2,mi,mj,max,p1;
  int matrix[10][10];
  int sumix[10][10];
  String p[8];

  cout<< "Input n: ";
  cin>> n;
  cout<< "Input m: ";
  cin>> m;
  cout<< "Created matrix [" << n << "x" << m << "]\n";
  p1=m+n-2;
  for(i=0;i<n;i++){
    for(j=0;j<m;j++){
      cout<<"Input matrix[" << i << "x" << j << "]=";
      cin>>matrix[i][j];
    }
  }
  for(i=0;i<n;i++){
    for(j=0;j<m;j++){
      cout<<matrix[i][j]<<" ";
    }
    cout<<"\n";
  }
  s1=0; s2=0;
  sumix[0][0]=matrix[0][0];
  max = sumix[0][0]; mi=0; mj=0;
  for(j=1;j<m;j++){
    sumix[0][j]=sumix[0][j-1] + matrix[0][j];
    if(sumix[0][j]>max){
      mj=j;
      max=sumix[0][j];
    }
  }
  for(i=1;i<n;i++){
    for(j=0;j<m;j++){
      if(j-1<0){
        sumix[i][j]=sumix[i-1][j] + matrix[i][j];
      }else{
        s1=sumix[i][j-1] + matrix[i][j];
        s2=sumix[i-1][j] + matrix[i][j];
        if(s1<s2)swap(s1,s2);
        sumix[i][j]=s1;
      }
      if(sumix[i][j]>=max){
        mi=i; mj=j;
        max=sumix[i][j];
      }
    }
  }
  max=matrix[n-1][m-1];
  while((mi+mj)!=0){
    if(mi==0 || mj==0){
      if(mi==0){
        mj--;
        p[p1]+="r";
        p1--;
      }else{
        mi--;
        p[p1]+="d";
        p1--;
      }
      max+=matrix[mi][mj];
    }else{
      if(sumix[mi-1][mj]>sumix[mi][mj-1]){
        mi--;
        p[p1]+="d";
        p1--;
      }else{
        mj--;
        p[p1]+="r";
        p1--;
      }
      max+=matrix[mi][mj];
    }
  };
  cout<<" Marshrut: ";
  for(i=0;i<(m+n-1);i++){
    cout<<p[i];
  }
  cout<<"\n Summa: " <<max <<"\n";
  cin>> n;
  return 0;
}

Akina

Дата 10.4.2008, 08:34 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Цитата(maxdiver @ 9.4.2008, 23:42

)

название алгоритму ты дал довольно оригинальное

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

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »