|
最优子矩阵是建立在数列连续最大和的基础上的。所谓最优子矩阵，就是指在一个n*m二维的矩阵中，确定一个小的矩阵，使这个小矩阵中所有元素的和最大。
思考一下最优子矩阵和连续最大和的异同：
1、 所求的和都具有连续性；
2、 连续最大和是一维问题，最优子矩阵是二维问题
另外，对于一个矩阵而言，如果我们将连续k行的元素纵向相加，并对相加后所得的数列求连续最大和，则此连续最大和就是一个行数为k的最优子矩阵！由此，我们可以将二维的矩阵压缩成一维矩阵，转换为线性问题，从而求解。
其实就是将二维的问题,换成一维
|
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 4 //matrix N*N
int getrand()
{
int num = rand()%11-5;
return num;
}
void print_matrix(int A[N][N])
{
int i;
int j;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
printf("%d\t",A[i][j]);
printf("\n");
}
}
int max_sub_array(int B[], int n)
{
int i = 0;
int sum = 0;
int max = 0;
for(;i<n;i++)
{
sum += B[i];
if(sum>max)
max = sum;
else if(sum<0)
sum = 0;
}
return max;
}
int max_sub_matrix(int A[N][N])
{
int i;
int j;
int k;
int last_i = 0;
int last_j = 0;
int max = 0;
int tmp = 0;
int array[N];
/*i=0,表示包含第一行的最大子矩阵 i=1...类推*/
for(i=0;i<N;i++)
{
for(k=0;k<N;k++)
array[k] = 0;
for(j=i;j<N;j++)
{
for(k=0;k<N;k++)
array[k] += A[j][k];
tmp = max_sub_array(array, N);
if(tmp>max)
{
last_i = i;
last_j = j;
max = tmp;
}
}
}
/*最大子矩阵开始和结束的行*/
printf("last_i is %d, last_j is %d\n",last_i+1, last_j+1);
return max;
}
int main(int argc, char *argv[])
{
int i;
int j;
int ret;
int A[N][N];
srand((unsigned int)time(NULL));
for(i=0;i<N;i++)
for(j=0;j<N;j++)
A[i][j] = getrand();
print_matrix(A);
ret = max_sub_matrix(A);
printf("max is %d\n",ret);
system("PAUSE");
return 0;
}
|
|
