从连续最大和到最优子矩阵.doc

从连续最大和到最优子矩阵。
2009-02-07 16:34
声明：此为转载，此篇也在noi专刊上刊登过。
从连续最大和到最优子矩阵
郑州市第101中学 2009届学生：史 沛
关键字：连续最大和 最优子矩阵 动态规划 矩阵数据压缩
从这次省选落选后，我发现有两个东西是自己极为欠缺的：1、动态规划；2、矩阵的相关知识；所以，这次好好地学习了一下矩阵和动态规划相结合的一些知识。为了以后能够铭记在心，特写一篇论文，一来，帮助那些还不清楚的OIers；二来，供自己日后参看。
——题记
一、 数列的连续最大和
在谈及最优子矩阵之前，我们先来做一些准备工作，即：数列的连续最大和，顾名思义，就是在一个长度为n的数列{An}中，求i，j（1<=i<=j<=n），使得数列{An}中，第i个元素到第j个元素之间，所有元素的和最大。
由于是连续，初学者往往想到的是枚举，然而枚举的时间复杂度是难以接受的。顾思考更高效的算法——动态规划。仔细思考题目后，符合动态规划条件。
用ans[i]表示包含数列第i项的前i个元素的最大和，数组no存放数列元素，则状态转移方程为：
ans[0]=0；
ans[i]=max{ans[i-1]+no[i],no[i]} 时间复杂度为O(n)
核心程序代码：
best:=-maxlongint;
temp:=0;
for i:=1 to n do
begin
inc(temp,no[i]);
if temp>best then best:=temp;
if temp<0 then temp:=0;
end;
注意：红色循环体部分的顺序万万不可颠倒！
[问题拓展]：在一个长度为n的数列{An}中，求m个连续子序列，使得这m个连续子序列的和最大，且m个子序列无公共元素。
解决类似的问题，我们可以利用“加一维”的思想利用动态规划来解决。
用ans[i,j]表示数列前j个元素中，i个无公共元素的子序列的最大和，且必须包含第j个元素，数组no存放数列元素，则状态转移方程为：
ans[i,j]=max{ans[i,j-1]+no[j],ans[i-1,k]+no[j]} (i-1<=k<=j-1) 时间复杂度为O(n^3)
何训程序代码：
for i:=1 to m do
for j:=i to n do
begin
ans[i,j]:=ans[i,j-1]+no[j];
for k:=i-1 to j-1 do if ans[i-1,k]+no[j]>ans[i,j] then ans[i,j]:=ans[i-1,k]+no[j];
end;
for i:=1 to n do if ans[m,i]>best then best:=ans[m,i];
注意：红色部分为确定最大值的过程！因为ans[i,j]表示数列前j个元素中，i个无公共元素的子序列的最大和，且最大和不一定非要取完所有的元素，所以用一个循环来检测所有m的连续子序列的元素最大和，以确定全局最优值！

二、 最优子矩阵
有了前面的铺垫，我们就可以导论最优子矩阵的问题了，换句话说，最优子矩阵是建立在数列连续最大和的基础上的。所谓最优子矩阵，就是指在一个n*m二维的矩阵中，确定一个小的矩阵，使这个小矩阵中所有元素的和最大。
思考一下最优子矩阵和连续最大和的异同：
1、 所求的和都具有连续性；
2、 连续最大和是一维问题，最优子矩阵是二维问题
另外，对于一个矩阵而言，如果我们将连续k行的元素纵向相加，并对相加后所得的数列求连续最大和，则此连续最大和就是一个行数为k的最优子矩阵！由此，我们可以将二维的矩阵压缩成一维矩阵，转换为线性问题，从而求解。故问题的关键在于如何用高效的压缩方式存储、读取矩阵。
下面具一个简单的例子。在一个一维的数列中，要想求从第i个元素到第j个元素的和，我们可以用这样的方法：设数组sum[i]表示从第1个到第i个元素的和，则：求从第i个元素到第j个元素的和，只需用sum[j]-sum[i]就足够了。由此推广到二维矩阵，设sum[i,j]表示矩阵第j列前i个元素的和，cost[i,j]表示原始数据，则：
压缩数据程序代码为：
for i:=1 to n do
for j:=1 to m do
sum[i,j]:=sum[i-1,j]+cost[i,j];
下一个问题是，如何将数据从压缩的数组中读出。下面，我们来分析、推导一下：
假设n=3的情况，不同的组合情况和数据处理方法如下表：(1<=j<=m)
不同的行组合
数据处理方法

第一行
sum[1,j]

第二行
sum[2,j]-sum[1,j]

第三行
sum[3,j]-sum[2,j]

第一、二行
sum[2,j]

第二、三行
sum[3,j]-sum[1,j]

第一、二、三行
sum[3,j]
我们将数据处理方法简写、并加以整理可得：
3-2，3-1，3-0
2-1，2-0，
1-0
不失一般性，可设两个循环变量，外层(i)从n到1，内层(j)从i-1到0。设数组temp用来存储临时的数列，则：
读取数据代码为：
for i:=n downto 1 do
for j:=i-1 downto 0 do
for k:=1 to m do temp[k]:=sum[i,k]-sum[j,k];
到此，最大子矩阵问题就完全转换为连续最大和问题。
[问题拓展]：在一个n*m二维的矩阵中，确定两个小的矩阵，使这两个小矩阵中所有元素的总和最大，且两个矩阵无公共元素。
既然是拓展，就与原问题有内在的联系，怎样的联系呢？我们先来看一下两个小矩阵的位置关系：
图暂略
图中给出了三种，其实，第二种和第三种可以算为一种，所有的情况无非这两种而已。对于第一种情况，可以枚举分割线（图中横线）的坐标，设其坐标为x，x从2到n逐个枚举，则可求出1到x-1行的左右自矩阵、从x到n行的最优子矩阵，二者的和如果大于当前最优值则更新。对于第二种情况，只需将原始矩阵的行、列交换，然后重复第一种情况的步骤即可。
大的框架有了，然而细节决定成败，压缩方式不变，关键还在于数据的读取！然而通过原问题的分析方式，我们可以和轻松的推导出数据的读取方法（具体方式请读者思考），即：
1、 外层(i)从x-1到1，内层(j)从i-1到0；
2、 外层(i)从n到x，内层(j)从i-1到x-1；

最后，求同存异。
附：论文中涉及的所有题目的标程。（在Free Pascal 1.98下调试通过）
program t1(input,output);{连续最大和}
var
no:array[1..1000] of longint;
n,best:longint;
{====================================}
procedure init;
var
i:longint;
begin
best:=-maxlongint;
assign(input,'t1.in');
assign(output,'t1.out');
reset(input);
rewrite(output);
readln(n);
for i:=1 to n do read(no[i]);
close(input);
end;
{====================================}
procedure solve;
var
i,temp:longint;
begin
temp:=0;
for i:=1 to n do
begin
inc(temp,no[i]);
if temp>best then best:=temp;
if temp<0 then temp:=0;
end;
writeln(best);
close(output);
end;
{====================================}
begin
init;
solve;
end.

program t2(input,output);{k个连续最大和}
var
n,m,best:longint;
no:array[1..1000] of longint;
ans:array[0..200,0..1000] of longint;
{====================================}
procedure init;
var
i:longint;
begin
best:=-maxlongint;
assign(input,'t2.in');
assign(output,'t2.out');
reset(input);
rewrite(output);
readln(n,m);
for i:=1 to n do read(no[i]);
close(input);
end;
{====================================}
procedure solve;
var
i,j,k:longint;
begin
for i:=1 to m do
for j:=i to n do
begin
ans[i,j]:=ans[i,j-1]+no[j];
for k:=i-1 to j-1 do
if ans[i-1,k]+no[j]>ans[i,j] then ans[i,j]:=ans[i-1,k]+no[j];
end;
for i:=1 to n do if ans[m,i]>best then best:=ans[m,i];
writeln(best);
close(output);
end;
{====================================}
begin
init;
solve;
end.

program t3(input,output);{最优子矩阵}
var
cost,sum:array[0..200,0..200] of longint;
temp:array[0..200] of longint;
n,m:longint;
{====================================}
procedure init;
var
i,j:longint;
begin
assign(input,'t3.in');
assign(output,'t3.out');
reset(input);
rewrite(output);
readln(n,m);
fillchar(cost,sizeof(cost),0);
fillchar(sum,sizeof(sum),0);
for i:=1 to n do
begin
for j:=1 to m do read(cost[i,j]);
readln;
end;
close(input);
for i:=1 to n do
for j:=1 to m do
sum[i,j]:=sum[i-1,j]+cost[i,j];
end;
{====================================}
procedure solve;
var
i,j,k,best,ans,tot:longint;
begin
tot:=-maxlongint;
for i:=n downto 1 do
for j:=i-1 downto 0 do
begin
for k:=1 to m do temp[k]:=sum[i,k]-sum[j,k];
ans:=-maxlongint;
best:=0;
for k:=1 to m do
begin
inc(best,temp[k]);
if best>ans then ans:=best;
if best<0 then best:=0;
end;
if ans>tot then tot:=ans;
end;
writeln(tot);
close(output);
end;
{====================================}
begin
init;
solve;
end.

program t4(input,output);{2个最优子矩阵}
var
cost,sum:array[0..200,0..200] of longint;
temp:array[0..200] of longint;
n,m,tot:longint;
{====================================}
procedure solve;
var
i,j,k,x,best1,best2,ans1,ans2:longint;
begin
tot:=-maxlongint;
for x:=2 to n do
begin
ans1:=-maxlongint;
for i:=x-1 downto 1 do
for j:=i-1 downto 0 do
begin
for k:=1 to m do temp[k]:=sum[i,k]-sum[j,k];
best1:=0;
for k:=1 to m do
begin
inc(best1,temp[k]);
if best1>ans1 then ans1:=best1;
if best1<0 then best1:=0;
end;
end;
ans2:=-maxlongint;
for i:=n downto x do
for j:=i-1 downto x-1 do
begin
for k:=1 to m do temp[k]:=sum[i,k]-sum[j,k];
best2:=0;
for k:=1 to m do
begin
inc(best2,temp[k]);
if best2>ans2 then ans2:=best2;
if best2<0 then best2:=0;
end;
end;
if ans1+ans2>tot then tot:=ans1+ans2;
end;
end;
{====================================}
procedure init;
var
i,j,swap:longint;
take:array[0..200,0..200] of longint;
begin
assign(input,'t4.in');
assign(output,'t4.out');
reset(input);
rewrite(output);
fillchar(sum,sizeof(sum),0);
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do read(cost[i,j]);
readln;
end;
close(input);
for i:=1 to n do
for j:=1 to m do
sum[i,j]:=sum[i-1,j]+cost[i,j];
solve;
swap:=m;
m:=n;
n:=swap;
fillchar(sum,sizeof(sum),0);
for i:=1 to n do
for j:=1 to m do
take[i,j]:=cost[j,i];
for i:=1 to n do
for j:=1 to m do
sum[i,j]:=sum[i-1,j]+take[i,j];
solve;
writeln(tot);
close(output);
end;
{====================================}
begin
init;
end.