最大子长方体问题

1、算法设计与分析课程设计题目： 最大子长方体问题 专业： 网络工程 班级： 学号： 姓名： 计算机工程系 2012年 11 月 16 日一、算法问题描述一个立方体被分割成n个小立方体，每个小立方体内有一个整数。试设计一个算法，计算出所给立方体的最大子长方体。子长方体的大小由它所含所有整数之和确定。二、算法问题形式化表示三、期望输入与输出输入：输入的第1行是3个正整数m,n,p，1m,n,p50。接下来m*n行每行p个正整数，表示小立方体中的数。 输出：输出的第1行中的数是计算出的最大子长方体的大小。样例输入：请输入立方体的长m,宽n,高p为：3 3 3m*n行中每行的p个正整数为：0 -1 21

2、 2 21 1 -2-2 -1 -1-3 3 -2-2 -3 1-2 3 30 1 32 1 -3样例输出：所给立方体的最大子长方体为：14四、算法分析与步骤描述 1算法总体过程 2最优值实现过程中信息的保存 在算法的实现过程中，是将原长方体分解成若干子长方体，每个子长方体都要转化成矩阵，求出各个矩阵的最大子矩阵，最优值就存在于这些最大子矩阵中，如果想获得最优解就必须对各个最大子矩阵的信息进行保存；同理，将子长方体转化成矩阵，分解成若干子矩阵，每个子矩阵都要转化成段，求出各个段的最大子段，要获得最大子矩阵，就得从这些最大子段中比较求得，如果想获得最优解就必须对各个最大子段和的信息进行保存，为此

3、，定义了下面的方法： static int max(int i,int j)if(i=j)return i;else return j; 3.算法的实现 最大子长方体问题的动态规划算法如下： static int MaxSum3(int a,int m,int n,int p)int sum=0;int b=new int 5050;int k,i,j,z,x;for(i=0;ip;i+)for(z=0;zm;z+)for(x=0;xn;x+)bzx=0;/初使化for( j=i;jp;j+)for(z=0;zm;z+)for(x=0;xn;x+)bzx+=azxj;sum=max(sum,M

4、axSum2(b,m,n);return sum; 其中MaxSum2()为最大子矩阵问题的动态规划算法，具体实现过程如下： static int MaxSum2(int a,int m,int n) /二维M*N的矩阵int sum=0;int b=new int50;int k=0;for(int i=0;im;i+)for(k=0;kn;k+)bk=0;for(int j=i;jm;j+)for(k=0;kn;k+)bk+=ajk;sum=max(sum,MaxSum(b,n);return sum;五、问题实例及算法运算步骤 设当前子长方体是最优子长方体，用num进行标志，其在i、j和

5、k方向上的起止位置分别为：(i1,i2)、(j1,j2)、(k1,k2)。k1、k2在算法MaxSum3中很容易确定，并已保存在three1,three2变量中；i1、i2要在MaxSum2中确定，它们的值保存在memtwonum.one1和memtwonum.one2中，由num1用来标志获得最优子长方体的最优子矩阵；j1、j2的值要在MaxSum1中确定，保存在memonenum1.two1和memonenum1.two2中，并在MaxSum2中赋值memtwonum.two1 =memonenum1.two1,memtwonum.two2=memonenum1.two2。若在MaxSum

6、3中判断出当前子长方体是当前的最优解，则进行赋值num3=num,num3最终保存的就是最优子长方体的标志。最优值确定后，进行赋值two1= memtwonum3.two1,two2=memtwonum3.two2,one1= memtwonum3.one1,one2= memtwonum3.one2,并通过如下算法，输出最大子长方体： for(int i=0;im;i+)for(int j=0;jn;j+)for(int k=0;kp;k+)aijk=Integer.parseInt(sc.next();System.out.println(所给立方体的最大子长方体为：);System.out.println(MaxSum3(a,m,n,p);六、算法运行截图七、算法复