实验七 动态规划 最大子矩阵问题
一、实验目的
1、分析并掌握"最大子矩阵" 问题的动态规划算法求解方法；
2、运用动态规划算法解决实际问题加深对动态规划算法的理解和运用；
二、实验环境
Windows XP以上版本的操作系统，Visual Studio 2010编程环境。
三、 实验内容
使用动态规划算法解决最大子矩阵问题，并能返回最大子矩阵的边界下标。
问题描述：给定一个m行n列的整数矩阵A，试求A的一个子矩阵，使其各元素之和为最大。
问题分析：用二维数组a[1:m][1:n]表示给定的m行n列的整数矩阵。子数组a[i1:i2][j1:j2]表示左上角和右下角行列坐标分别为(i1,j1)和(i2,j2)的子矩阵，其各元素之和记为：
最大子矩阵问题的最优值为。
如果用直接枚举的方法解最大子矩阵和问题，需要O(m^2n^2)时间。注意到，式中，，设，则
容易看出，这正是一维情形的最大子段和问题。因此，借助最大子段和问题的动态规划算法MaxSum，可设计出最大子矩阵和动态规划算法
参考：最大字段和动态规划算法：
int MaxSum(int n,int *a)
{
int sum=0,b=0;
for(int i=1; i<=n; i++)
{
if(b>0)
{
b+=a[i];
}
else
{
b=a[i];
}
if(b>sum)
{
sum = b;
}
}
return sum;
}
《第07周实验七最大子矩阵和问题》相关文档：
第07周实验七最大子矩阵和问题09-12
