最大子矩阵问题
最优子矩阵是建立在数列连续最大和的基础上的。所谓最优子矩阵,就是指在一个n*m二维的矩阵中,确定一个小的矩阵,使这个小矩阵中所有元素的和最大。思考一下最优子矩阵和连续最大和的异同:
1、 所求的和都具有连续性;
2、 连续最大和是一维问题,最优子矩阵是二维问题
另外,对于一个矩阵而言,如果我们将连续k行的元素纵向相加,并对相加后所得的数列求连续最大和,则此连续最大和就是一个行数为k的最优子矩阵!由此,我们可以将二维的矩阵压缩成一维矩阵,转换为线性问题,从而求解。
其实就是将二维的问题,换成一维
#include
#include
#include
#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
{
for(j=0;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
{
sum += B[i];
if(sum>max)
max = sum;
else if(sum
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
{
for(k=0;k
array[k] = 0;
for(j=i;j
{
for(k=0;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
for(j=0;j
A[i][j] = getrand();
print_matrix(A);
ret = max_sub_matrix(A);
printf("max is %d\n",ret);
system("PAUSE");
return 0;
}