深搜与简单的动态规划

深搜与简单的动态规划第1页，课件共48页，创作于2023年2月深度优先搜索算法的框架:proceduredfs(i);//搜索第i个分量Xibeginifi=n+1找到一个解

//ifi=n+1thenexit;//防止数组越界

//合适的剪枝优化：最优化剪枝与可行性剪枝forXi

∈Si且使得（X1,X2，。。。Xi-1,Xi）满足约束条件dobegin记录满足条件的Xi;//添加相应的标志;dfs(i+1)//删除标志;恢复之前的状态,根据具体情况选择:回溯endend第2页，课件共48页，创作于2023年2月1、数字三角形

有一个数字三角形，编程求从最顶层到最底层的一条路所经过位置上数字之和的最大值。每一步只能向左下或右下方向走。下图数据的路应为7->3->8->7->5，和为30。输入：第一行：R(1<=R<=100),数字三角形共有R行；以下R行：依次表示数字三角形中每行中的数字。每个数都是非负的，且<=100.输出：一个正整数，路径上数字之和的最大值。输入样例：5738810274445265输出样例：30

738810274445265第3页，课件共48页，创作于2023年2月算法1：深度优先搜索算法DFS：二维数组a[i，j]存储数字三角形。Proceduredfs(sum,i,j:integer);//从a[1,1]到走到第i行第j列即a[i,j]时所取得的值为sumbeginifi=nthenbeginifsum>maxthenmax:=sum;exit;end;

dfs(sum+a[i+1,j],i+1,j);//向左下方走

dfs(sum+a[i+1,j+1],i+1,j+1);//向右下方走end;开始时：dfs(a[1,1],1,1);结果：max

738810274445265第4页，课件共48页，创作于2023年2月

738810274445265为什么当n较大时速度慢？f:array[0..100,0..100]ofinteger;f[i,j]:(i,j)到最后一行经过数的和的最大值f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j];初始：f[n,i]=a[n,i]目标：f[1,1]第5页，课件共48页，创作于2023年2月算法2：functionmax(a,b:longint):longint;beginifa>bthenexit(a)elseexit(b);end;Proceduredfs(i,j:integer);

//求(i,j)到最后一行的最大和

beginifi=nthenbeginf[i,j]:=a[i,j];exit;end;iff[i,j]>0thenexit;dfs(i+1,j);dfs(i+1,j+1);f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j];end;第6页，课件共48页，创作于2023年2月Begininit;fillchar(f,sizeof(f),0);dfs(1,1);writeln(f[1,1]);End.第7页，课件共48页，创作于2023年2月设f[i,j]:a[i,j]到达第n行a[n,k]（k：1..n）的最大值．递推关系：f[i,j]=max{f[i+1,j],f[i+1,j+1]｝+a[i,j]初始：f[n,i]:=a[n,i];1=<i<=n目标：f[1,1]算法3：

73881027

4445265第8页，课件共48页，创作于2023年2月proceduremain;beginfori:=1tondof[n,i]:=a[n,i];fori:=n-1downto1do{枚举行}forj:=1toido{枚举每行的元素}

f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[I,j];{枚举走法}writeln(f[1,1]);end;

functionmax(a,b:integer):integer;beginmax:=a;ifb>maxthenmax:=b;end;第9页，课件共48页，创作于2023年2月依次求从起点(1,1)到点（i，j）的最大值。//正向设f[i,j]为从a[1,1]到达a[i,j]时取得的最大值．根据题意可得出递推关系：f[i,j]=max{f[i-1,j-1],f[i-1,j]｝+a[i,j]初始：f[1,1]:=a[1,1];目标：max{f[n,i]}1=<i<=n

73881027

4445265

算法4：第10页，课件共48页，创作于2023年2月proceduremain;{顺推}beginf[1,1]:=a[1,1];fori:=2tondoforj:=1toidof[i,j]:=max(f[i-1,j-1],f[i-1,j])+a[i,j];ans:=f[n,1];fori:=2tondoiff[n,i]>ansthenans:=f[n,i];writeln(ans);end;第11页，课件共48页，创作于2023年2月总结：算法1：一般的搜索（效率很低）。算法2：记忆化搜索（效率高）。算法3和算法4：动态规划算法（效率高）。第12页，课件共48页，创作于2023年2月在一个n*m的棋盘内，一些格子里有垃圾要拾捡。现在有一个能捡垃圾的机器人从左上格子里出发，每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内的垃圾拾掉。问：机器人到达右下角时最多能拾多少垃圾。数据范围:n<=100,m<=1002、Robots机器人捡垃圾第13页，课件共48页，创作于2023年2月样例输入：67712142426444766样例输出：5第14页，课件共48页，创作于2023年2月算法1：dfsC[i,j]=1表示(i,j)点有垃圾。C[i,j]=0表示没有。proceduredfs(i,j,sum:longint);//从(i,j)走到终点(n,m)能捡到的垃圾数是sumbeginif(i=n)and(j=m)thenifsum>ansthenans:=sum;ifi<nthendfs(i+1,j,sum+c[i+1,j]);ifj<mthendfs(i,j+1,sum+c[i,j+1]);end;初始：dfs(1,1,c[i,j])结果是：ans第15页，课件共48页，创作于2023年2月算法2:因为只能向右或者向下走。也就是说不能走回头路。设f[i,j]表示从(1,1)点开始走到(i,j)的时候，最多捡了多少垃圾。根据(i,j)只能从(i-1,j)或者(i,j-1)走过来。得出递推关系:f[i,j]=Max{f[i-1,j],f[i,j-1]}+c[i,j]初始：f[0,i]=0;0<=i<=m;f[j,0]=0;0<=j<=n;目标：f[n,m]第16页，课件共48页，创作于2023年2月简单的主程序：Fillchar(f,sizeof(f),0);fori:=1tondoforj:=1tomdof[i,j]:=max(f[i,j-1],f[i-1,j])+c[i,j];Writeln(f[n,m]);第17页，课件共48页，创作于2023年2月3：简单的背包问题(0-1背包)

设有ｎ种物品，每种物品有一个重量及一个价值。同时有一个背包，最大载重量为M，今从ｎ种物品中选取若干件，使其重量的和小于等于m，而价值的和为最大。N<=100,M<1000.

输入数据：

第一行两个数：物品总数Ｎ，背包载重量M；两个数用空格分隔；

第二行N个数,为Ｎ种物品重量Wi(<1000)；两个数用空格分隔；

第三行N个数,为N种物品价值Vi(<1000);两个数用空格分隔；

输出数据：

总价值；输入样例1：

410

4357

1572025

输出样例1：

35输入样例2：

420

291015

291016

输出样例2：

19第18页，课件共48页，创作于2023年2月Dfs算法:constmaxn=100;varn,m:integer;//n：物品数量；m：背包容量

w:array[1..maxn]ofinteger;//物品重量

v:array[1..maxn]ofinteger;//物品价值

best:longint;//最大价值

第19页，课件共48页，创作于2023年2月proceduredfs(i,left,value:longint);//i：搜索第i件物品:判断放还是不放到背包里

//left：背包的剩余空间

//value：已装物品的价值

beginifi=n+1thenifvalue>bestthenbest:=value;

ifi>nthenexit;//防止溢出

dfs(i+1,left,value);//不装iifleft>=w[i]then//装i

dfs(i+1,left-w[i],value+v[i]);end;第20页，课件共48页，创作于2023年2月主程序：

init;dfs(1,m,0);writeln(best);第21页，课件共48页，创作于2023年2月0123456789100000000000001000015151515151515200071515152222222230007152020222735354000715202025273535背包的容量0--10物品0--4编号1234容量4357价值15720254件物品背包容量：10算法2：设f[i,j]:从1到i件物品中选若取干件放到容量为j的背包中，获得的最大价值。目标是：f[n,m]第22页，课件共48页，创作于2023年2月用f[i,j]表示在第１到第i件物品中装入重量为j的背包获得的最大价值．f[i,j]=max{f[i-1,j],f[i-1,j-W[i]]+V[i]}(1<=i<=n,1<=j<=m)目标：f[n,m];2)f[i-1,j-W[i]]+V[i]：放第i件的价值。条件：j>=w[i]1)f[i-1,j]:不放第i件物品获得的价值。第23页，课件共48页，创作于2023年2月主程序：

fillchar(f,sizeof(f),0);fori:=1tondo

forj:=1tomdobeginf[i,j]:=f[i-1,j];

//不选择第i件物品

if(j>=w[i])and(f[i,j]<f[i-1,j-w[i]]+v[i])//选择第i件物品｝

thenf[i,j]:=f[i-1,j-w[i]]+v[i];end;writeln(f[n,m]);end.第24页，课件共48页，创作于2023年2月4：求最大连续子序列的和输入：第一行：n（N<10000）第二行：n个整数（-3000，3000）。输出：最大连续子序列的和。样例：输入：7-64-13

2-32输出：8第25页，课件共48页，创作于2023年2月算法1：枚举任意连续区间求和找最大值

readln(n);fori:=1tondoread(a[i]);ans:=-30000000;fori:=1tondoforj:=itondobeginsum:=0;fork:=itojdosum:=sum+a[k];ifsum>ansthenans:=sum;end;writeln(ans);时间：O(n3)理想的算法：<=106第26页，课件共48页，创作于2023年2月算法2：算法1的优化

readln(n);fori:=1tondoread(a[i]);ans:=-30000000;fori:=1tondobeginsum:=0;forj:=itondobeginsum:=sum+a[j];ifsum>ansthenans:=sum;end;end;writeln(ans);

时间：O(n2)第27页，课件共48页，创作于2023年2月算法1和算法2是把n个数看作独立的没有联系的数来处理的。1、以a[i]为结束点和以a[i+1]为结束点的最大连续子序列有没有联系？有什么样的联系？2、f[i]：从第1项开始，以a[i]为终点（右边界）的子序列的最大和。如果事先已经求得了以a[i]为结束点的最大连续子序列和为f[i]，那么怎样求以a[i+1]为结束点的最大连续子序列？-64-132-32第28页，课件共48页，创作于2023年2月算法3：a[i]:存储序列；f[i]：从第1项开始，以a[i]为终点（右边界）的子序列的最大和。f[i]=max{f[i-1]+a[i],a[i]}：即看f[i-1]的正负初始：f[1]=a[1]目标：max{f[i]}1<=i<=nproceduredp;beginf[1]:=a[1];fori:=2tondof[i]:=max(f[i-1]+a[i],a[i]);ans:=f[1];fori:=2tondoiff[i]>ansthenans:=f[i];end;时间：O(n)第29页，课件共48页，创作于2023年2月在一个n×m的方格中，m为奇数，放置有n×m个数，如图1643126034-56700260-1-236853400-27-17407-560-1341242人方格中间的下方有一人，此人可按照五个方向前进但不能越出方格。如所示：

5取数n,m<=100,方格数[-100，100]第30页，课件共48页，创作于2023年2月样例输入：671643126034-56700260-1-236853400-27-17407-560-1341242样例输出：51第31页，课件共48页，创作于2023年2月f[i,j]:人走到（i，j）时得数的最大值。f[i,j]=max{f[i+1,j-2],f[i+1,j-1],f[i+1,j],f[i+1,j+1],f[i+1,j+2]}+a[i,j]第32页，课件共48页，创作于2023年2月

proceduredp;begink:=mdiv2+1;fori:=k-2tok+2dof[n,i]:=a[n,i];fori:=n-1downto1doforj:=max(1,k-2*i)tomin(k+2*i,m)dobeginf[i,j]:=-10001;fork:=-2to2doif(k+j>=1)and(k+j<=m)and(f[i+1,k+j]>f[i,j])thenf[i,j]:=f[i+1,k+j];f[i,j]:=f[i,j]+a[i,j];end;ans:=f[1,1];fori:=2tomdoiff[1,i]>ansthenans:=f[1,i];writeln(ans);end;第33页，课件共48页，创作于2023年2月6迷宫寻宝一个n行m列的迷宫（1<=n,m<=50），入口在左上角，规定只能向下或向右走。迷宫的某些地方藏有不同价值的宝藏，同时有存在一些障碍无法通过。求到达右下角出口时收集的宝藏的最大值。输入：第一行n和m，n行m列：迷宫矩阵a[i,j]（-1：障碍）保证a[1,1]<>-1。输出：最大值。样例：输入2：54213-11-1-1-12-120-13125-11-12输出2：18输入1：342-15051

3-16-18910输出1：33第34页，课件共48页，创作于2023年2月i,ji,j+1i+1,ji-1,ji,j-1i,j第35页，课件共48页，创作于2023年2月分析：逐行扫描

a[i,j]保存第i行第j列的宝藏价值．

f[i,j]走到第i行第j列时所能收集的宝藏的最大价值．状态转移方程：

f[i,j]=max{f[i-1,j],f[i,j-1]}+a[i,j](1<=n,1<=m)

条件:a[i,j]<>-1时.

初始：f[1,1]=a[1,1];

目标：f[n,m]第36页，课件共48页，创作于2023年2月functionmax(a,b:integer):integer;beginmax:=a;ifb>athenmax:=b;end;proceduredp;beginfillchar(f,sizeof(f),0);fori:=1tondoforj:=1tomdoifa[i,j]<>-1thenf[i,j]:=max(f[i-1,j],f[i,j-1])+a[i,j];end;？第37页，课件共48页，创作于2023年2月-1-120第38页，课件共48页，创作于2023年2月读入数据的预处理：

ifa[i-1,j]=-1anda[i,j-1]=-1thena[i,j]=-1varf,a:array[0..maxn,0..maxm]ofinteger;{加边界，减少判断越界}

readln(n,m);fori:=0ton+1do{初始全是障碍}forj:=0tom+1doa[i,j]:=-1;a[0,1]:=0;{保证a[1,1]能到达}fori:=1tondoforj:=1tomdobeginread(a[i,j]);if(a[i,j-1]=-1)and(a[i-1,j]=-1)thena[i,j]:=-1;end;342-150513-16-18910第39页，课件共48页，创作于2023年2月某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统（能发射任意发炮弹）。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都要求高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入敌国导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹7、拦截导弹第40页，课件共48页，创作于2023年2月输入:

第一行：n（<=1000），敌国导弹的数量。依次是敌国导弹的高度(<30000)。输出：最多拦截敌国导弹的数量。样例：输入：8271910123输出：4第41页，课件共48页，创作于2023年2月转化：

求最长的递增子序列