Дали такую задачу:

Цитата

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

Может, кто с такой задачей сталкивался. Я понимаю, что бывает и сложнее, но тут неясно, задаётся ли размерность подматрицы...
Спасибо за помощь.

NiJazz, ну значит примерно так:
1. Берем первый эл-т матрицы и прибавляем к нему следующий эл-т строки до N потом идем по столбцам до M (где N - колво эл-ов в строке матрицы, М - количество строк в матрице) , таким образом получаем макс. сумму эл-ов и это и является подматрицей данной матрицы, что не противоречит ни условию ни определению.

2. Следовательно если задана размерность (а она должна быть задана) то в пункте 1 идем не до N и M, а до n и m, n и m - размерность подматрицы. перебирая элементы матрицы находим макс. сумму эл-ов
(перебираем элементы с индекса (1,1) до (N-n,M-m))

3. Желательно еще запоминать начальный индекс, подматрицы в матрице, которая дает макс. сумму эл-ов на текущей иттерации. Чтобы потом не было проблем с выводом на экран

Это сообщение отредактировал(а) Dr.Drunk - 26.4.2004, 10:09

Строго говоря, существует такой способ.
Примем во внимание, что скорее всего такая матрица содержит один из максимальных n элементов. Если элементов n, то в матрице точно содержиться элемент не ниже dim(need_matrica)/N*N(или в случае достаточно гладкого распределения N_max*((m/n)^2)),( В данном случае dim-число элементов) что уже облегачает задачу. Далее следует рисковый кусок: весь массив нормируем на этот элемент и ищем куски подходящей размерности содержащие максимальную плотность ненулевых элементов(основная чать массива после нормировки 0). Скорее всего 1 из трех-четырех таких кусков и есть нужная матрица.
Не хочешь рисковать другой способ- тестить только куски содержащие ненулевые элементы.
Скорость варианта Dr.Drunka-O((N-m)*(N-m)*scorost_summirovania_matr_m*m);
Данный вариант.O((N^2)*scorost_sdviga+(N/2)*scorost_summirovania_matr_m*m);
Думайте сами, решайте сами.

Если кому интересно, вот как я сделал. Сделано совсем без премудростей, наверняка есть варианты более эффективной реализации. Но, главное, что работает.
Я очень жду отзывов и рекомендаций.

Цитата

#include <iostream.h> #include <stdlib.h> #include <conio.h> #include <mem.h> #define row_count 4 #define col_count 5 void InitAndPrintMatrix(int matr[row_count][col_count]) {   clrscr();   randomize();   memset(matr, 0, row_count*col_count*sizeof(int));   cout << "Исходная матрица:" << endl << endl;   for (int i=0;i<row_count;i++)   {       for (int j=0;j<col_count;j++)       {   matr[i][j] = rand()%99 + 1;   cout << matr[i][j];   if (matr[i][j] / 10 == 0)     cout << "  ";   else     cout << " ";       }       cout << endl;   }   cout << endl; } int FindAndPrintSubmatrix(int matr[row_count][col_count]) {   int subrow = 0;   int subcol = 0;   cout << "Введите размерность подматрицы. " << endl;   cout << "Количество строк: ";   cin >> subrow;   if ((subrow>row_count) || (subrow<1))   {       cout << "Неверное значение!" << endl;       return 0;   }   cout << "Количество столбцов: ";   cin >> subcol;   if ((subcol>col_count) || (subcol<1))   {       cout << "Неверное значение!" << endl;       return 0;   }   int sum = 0;   int maxsum = 0;   int maxrow = 0;   int maxcol = 0;   for (int i=0;i<row_count-(subrow-1);i++)   {       for (int j=0;j<col_count-(subcol-1);j++)       {   for (int k=0;k<subrow;k++)   {     for (int l=0;l<subcol;l++)     {         sum = sum + matr[i+k][j+l];     }   }   if (maxsum < sum)   {     maxsum = sum;     maxrow = i+1;     maxcol = j+1;   }   sum = 0;       }   }   cout << endl;   cout << "Вот искомая матрица:" << endl << endl;   for (i=maxrow-1;i<maxrow-1+subrow;i++)   {       for (int j=maxcol-1;j<maxcol-1+subcol;j++)       {   cout << matr[i][j];   if (matr[i][j] / 10 == 0)     cout << "  ";   else     cout << " ";       }       cout << endl;   }   return 1; } void main() {   int matr[row_count][col_count];   InitAndPrintMatrix(matr);   if (!FindAndPrintSubmatrix(matr))       return;   cin.get();   cin.get(); }

DenDen вот матрица для которой твой алгоритм не сработает

55 1 1 0
1 0 0 0
1 0 0 56

подматрица размером 2Х3 или 3х2
Добавлено @ 07:23
NiJazz, что и требовалось доказать просто и главное ответ правильный получил


Это сообщение отредактировал(а) Dr.Drunk - 27.4.2004, 07:19

Dr.Drunk, почему не сработает? Он просто выведет не все матрицы.