поиск пути

[NiCola999]

допустим вот такая доска с числами
m:
0 1 2
3 2 5
1 0 6
черепашка стоит в m[0][0]
вот матрица максимумов
tmp[i][j] = max(m[i+1][j], m[i][j+1]) + m[i][j]

tmp:
3 3 0
5 7 0
0 0 0

как используя эту матрицу переместить черепашку в m[3][3] ?))
возможные ходы черепашки i+1(вниз) и j+1(вправо)

[LeBron]

Сообщение от NiCola999

tmp[i][j] = max(m[i+1][j], m[i][j+1]) + m[i][j]

tmp:
3 3 0
5 7 0
0 0 0

как используя эту матрицу переместить черепашку в m[3][3] ?))

Матрица не имеет смысла, посмотрите еще раз на мой пост с формулой, она немного иначе выглядит.
З.Ы. Для вашего примера комп выдал матрицу, содержание которой такое:
16 14 13
16 13 11
7 6 6

[NiCola999]

препод дал вот это =)

tmp[i][j] = max( a[i-1][j], a[i][j-1] + tmp[i][j]);

[Serge_Bliznykov]

вот моё решение. основано на рекурсии.
логика очень простая. разобраться сможете легко.

НО. может Вашему преподавателю это и не понравится...

const NMax = 100; MMax = 100;
var
  input, output: text;
  ar: array[1..NMax, 1..MMax] of longint;
  N, M : integer;
  i, j : integer;
  MaxPath : Integer;
  ThePath : string;

function IntToStr(k:integer) : string;
var s : string;
begin
  Str(k, s);
  IntToStr := s;
end;


function fCountPath(const x,y : integer; var SPath : string) : integer;
var SumPathRigth, SumPathDown : integer;
  s1, s2 : string;
begin
  if (x=N) and (y=M) then begin
     {Path := Path + ' ['+IntToStr(x)+','+IntToStr(y)+']';}
     SPath := ' ['+IntToStr(x)+','+IntToStr(y)+']';
     fCountPath := ar[x,y];
  end
  else begin
    s1 := SPath; s2 := SPath;

    if x<N then SumPathRigth := ar[x,y]+fCountPath(x+1,y, s1)
           else SumPathRigth := ar[x,y];
    if y<M then SumPathDown := ar[x,y]+fCountPath(x,y+1, s2)
           else SumPathDown := ar[x,y];
    if (x<N) and (SumPathRigth>SumPathDown) then begin
      {сейчас вправо идти выгоднее и возможно}
      SPath := ' ['+IntToStr(x)+','+IntToStr(y)+']' + s1;
      fCountPath := SumPathRigth
    end
    else begin
      {сейчас вниз идти выгоднее}
      SPath := ' ['+IntToStr(x)+','+IntToStr(y)+']' + s2;
      fCountPath := SumPathDown
    end;
  end;
end;

begin
  { прочитаем исходные данные}
  assign(input, 'input.txt');
  reset(input);
  readln(input, N, M);
  if (N>100) or (M>100) then begin
    WriteLn('Числа слишком большие. Не допускается матрица более ',
             NMax:1,'x',MMax:1);
    Halt(100);
  end;

  {читаем входной файл}
  for i := 1 to N  do begin
    for j := 1 to M do begin
      read(input, ar[i, j]);
    end;
    readln(input);
  end;

  {выводим исходную матрицу на экран.}
  WriteLn('Исходная матрица:');
  for i := 1 to N do begin
    for j := 1 to M do begin
      Write(ar[i, j]:3);
    end;
    WriteLn;
  end;

  {вот эти две строки есть нахождение пути с максимальным весом}
  ThePath := '';
  MaxPath := fCountPath(1,1, ThePath);

  {вывод результатов}
  WriteLn('Максимальное величина = ',MaxPath:1);
  WriteLn('Путь : ', ThePath);

end.

p.s. входной файл такой же как у LeBron
вначале строки файл input.txt два числа: число_строк и число_столбцов
потом построчно матрица.
варианты файлов input.txt:

первый вариант (был в топике)
3 4
1 2 9 2
4 3 8 1
1 1 1 1

второй вариант. (просто случайный набор):
5 5
1 1 1 1 1
1 3 1 1 1
1 5 1 11 1
1 1 1 12 1
9 5 1 1  2

удачи.

[NiCola999]

да распишите кто-нибудь алгоритм решения с помощью динамического программирования, а не рекурсии, не надо код.Или хотя бы если код то на с/с++

[LeBron]

Даже не знаю, я раньше уже написал, как она решаеться... Если надо объяснить "с ноля", то попытаюсь... не знаю, получиться ли, объясняю я так же, как пишу код. В общем, нам надо найти максимальную цену пути к правому нижнему углу. Цена пути с правого нижнего угла к правому нижнему углу равна весу клетки, которая в этом углу (ведь на матрице 1 на 1 не получиться набрать больше). Дальше для каждой клетки находим максимальную сумму, которую можно набрать, начиная с этой клетки. Логика такая: в сумму будет входить вес этой клетки и вес пути до последней клетки с этой клетки (уже без учета самого веса этой клетки). С текущей клетки в сторону последней клетки можно выйти 2мя способами - сделав ход вправо или сделав ход вниз. Смотрим, какой из этих путей более "дорогой" (для какой из 2 клеток мы перед этим получили болшее значение цены пути) и для получения значения пути с данной клетки суммируем значение пути с той, более дорогой, клетки, и значение клетки (именно самой клетки, то значение, которое получили вначале с входного файла), которую мы рассматриваем. Так обходим всю матрицу снизу вверх справа налево (иначе у нас в процессе обхода будет получаться, что для определения значения пути данной клетки нужно оценить значения путей для клеток, для которых мы это значение еще не вычислили), пока не попадем в начальную клетку. В результате получим цену пути. А для вывода самого пути будем действовать почти так же, как действовали при заполнении, только в другую сторону - выйдем с начальной клетки и каждый раз будем переходить в ту клетку с двох доступных для хода, где больше значение пути.

[Serge_Bliznykov]

распишите кто-нибудь алгоритм решения с помощью динамического программирования, а не рекурсии

сорри, я — пасс...
BTW, а что такое, в вашем понимании, "динамическое программирование" ?

[LeBron]

Сообщение от Serge_Bliznykov

сорри, я — пасс...
BTW, а что такое, в вашем понимании, "динамическое программирование" ?

Гугль в помощь. ДП - оно и в Африке ДП. Я уже вверху расписал дважды.
From Stilet:Господа, ссоры и кабаки до цугундера доведут. Закрою за флуд.

[Serge_Bliznykov]

LeBron, вопрос про динамическое программирование обращён НЕ К ВАМ! поэтому не стоило на него отвечать. тем более, посылать меня в поиск. Или в Гугле так и забить - ДП с точки зрения NiCola999 ?!
From Stilet:Господа, ссоры и кабаки до цугундера доведут. Закрою за флуд.

[NiCola999]

разбиение большой задачи на мелкие и их решение. Задача разбивается на подзадачи. В моем случае это заполнение матрицы максимумами очков препод дал такую формулу
1)B[i][j] = max( A[i-1][j], B[i][j-1] + A[i][j]);
или может так
2)B[i][j] = max( A[i-1][j], B[i][j-1] ) + A[i][j];

в тетради просто написана)
думаю 2ое
Затем используя эту матрицу ищется путь, как не знаю

Смотрим, какой из этих путей более "дорогой" (для какой из 2 клеток мы перед этим получили болшее значение цены пути) и для получения значения пути с данной клетки суммируем значение пути с той, более дорогой, клетки, и значение клетки (именно самой клетки, то значение, которое получили вначале с входного файла), которую мы рассматриваем.

вот это не очень понял

используя эту формулу
B[i][j] = max( A[i-1][j], B[i][j-1] ) + A[i][j];

для матрицы A:
0 1 2
3 2 5
1 0 6

получил такую матрицу B:
0 0 0
0 3 8
0 2 11
я правильно тебя понял LeBron ? )
начинаем цикл с нижнего угла, значит используем правило хода наоборот( вверх,влево), смотрим если сверху от клетки B[2][2] стоит большее число,чем слева, передвигаем вверх (i-1) , иначе (j-1).
получилось вот что...

for( i=size-1,j=size-1; i!=0 && j!=0;)
    {             
             printf("pos( %d ; %d )\t%d\n", i,j,B[i][j]);
              k+=B[i][j];      
               if( B[i-1][j] > B[i][j-1] )
                    i--;
               else
                    j--;                                                    
    }
    printf("Scores: %d\n", k);

pos( 2 ; 2 ) 11
pos( 1 ; 2 ) 8
pos( 1 ; 1 ) 3
Scores: 22

идет вроде правильно, останавливается на 3ке т.к там дальше нули идут и условие не выполняется. Вот не пойму как сделать чтобы она правильно пошла в таком случае и не зашла за границы матрицы

p.s я хоть на правильном пути ?)