深搜与简单的动态规划.ppt

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,深搜与简单的动态规划,深度优先搜索算法的框架,:,procedure dfs(i);/,搜索第,i,个分量,Xi,begin,if i=n+1,找到一个解,/if i=n+1 then exit;/,防止数组越界,/,合适的剪枝优化：最优化剪枝与可行性剪枝,for,Xi,Si,且使得（,X1,X2,，。Xi-1,Xi）满足约束条件 do,begin,记录满足条件的Xi;,/添加相应的标志;,dfs(i+1),/删除标志;恢复之前的状态,根据具体情况选择:回溯,end,end,1,、数字三角形,有一个数字三角形，编程求从最顶层到最底层的一条路所经过位置上数字之和的最大值。每一步只能向左下或右下方向走。下图数据的路应为,7-3-8-7-5,，和为,30,。,输入：,第一行：,R(1=R=100),数字三角形共有,R,行；,以下,R,行：依次表示数字三角形中每行中的数字。,每个数都是非负的，且,max then max:=sum;exit;end;,dfs,(sum+ai+1,j,i+1,j);/,向左下方走,dfs,(sum+ai+1,j+1,i+1,j+1);/,向右下方走,end;,开始时：,dfs(a1,1,1,1);,结果：,max,7,3 8,8,1,0,2 7 4 4,4 5 2 6 5,7,3 8,8 1 0,2 7 4 4,4 5 2 6 5,为什么当,n,较大时速度慢？,f:array0.100,0.100 of integer;,fi,j,:(i,j),到最后一行经过数的和的最大值,fi,j:=max(fi+1,j,fi+1,j+1)+ai,j;,初始：,fn,i=an,i,目标：,f1,1,算法,2,：,function max(a,b:longint):longint;,begin if ab then exit(a)else exit(b);end;,Procedure dfs(i,j:integer);,/,求,(i,j),到最后一行的最大和,begin,if i=n then,begin fi,j:=ai,j;exit;end;,if fi,j0 then exit;,dfs(i+1,j);,dfs(i+1,j+1);,fi,j:=max(fi+1,j,fi+1,j+1)+ai,j;,end;,Begin,init;,fillchar(f,sizeof(f),0);,dfs(1,1);,writeln(f1,1);,End.,设,fi,j:ai,j,到达第,n,行,an,k,（,k,：,1.n,）的最大值,递推关系：,fi,j=maxfi+1,j,fi+1,j+1,+ai,j,初始：,fn,i:=an,i;1=imax then max:=b;end;,依次求从起点,(1,1),到点（,i,，,j,）的最大值。,/,正向,设,fi,j,为从,a1,1,到达,ai,j,时取得的最大值,根据题意可得出递推关系：,fi,j=maxfi-1,j-1,fi-1,j,+ai,j,初始：,f1,1:=a1,1;,目标：,maxfn,i 1=ians then ans:=fn,i;,writeln(ans);,end;,总结：,算法,1,：一般的搜索（效率很低）。,算法,2,：记忆化搜索（效率高）。,算法,3,和算法,4,：动态规划算法（效率高）。,dfs(i+1,j+1);,/添加相应的标志;,根据题意可得出递推关系：,第二行：n个整数（-3000，3000）。,Fillchar(f,sizeof(f),0);,if ai-1,j=-1 and ai,j-1=-1 then ai,j=-1,for j:=1 to m do,2、Robots 机器人捡垃圾,if in then exit;/防止溢出,f1:=a1;,2 7 1 9 10 1 2 3,for i:=1 to n do,在一个,n*m,的棋盘内，一些格子里有垃圾要拾捡。现在有一个能捡垃圾的机器人从左上格子里出发，每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内的垃圾拾掉。,问：机器人到达右下角时最多能拾多少垃圾。,数据范围,:n=100,m,ans,then,ans,:=sum;,if in then dfs(i+1,j,sum+ci+1,j);,if jm then dfs(i,j+1,sum+ci,j+1);,end;,初始：,dfs(1,1,ci,j),结果是：,ans,fi,j:=-10001;,readln(n);,fi,j:=fi-1,j;/不选择第i件物品,fi+1,j+1,/从a1,1到走到第i行第j列即ai,j时所取得的值为sum,fi:以ai为结尾(ai是最后一个元素,即包含ai)的最长递增子序列的序列长度。,then fi,j:=fi-1,j-wi+vi;,/从(i,j)走到终点(n,m)能捡到的垃圾数是sum,dfs(1,1);,有一个数字三角形，编程求从最顶层到最底层的一条路所经过位置上数字之和的最大值。,dfs(i+1,left-wi,value+vi);,writeln(ans);,end,if i=n then,for i:=2 to n do,writeln(ans);,Ci,j=1表示(i,j)点有垃圾。,算法,2:,因为只能向右或者向下走。也就是说不能走回头路。,设,fi,j,表示从,(1,1),点开始走到,(i,j),的时候，最多捡了多少垃圾。,根据,(i,j),只能从,(i-1,j),或者,(i,j-1),走过来。,得出递推关系,:,fi,j=Maxfi-1,j,fi,j-1+ci,j,初始：,f0,i=0;0=i=m;,fj,0=0;0=j=n;,目标：,fn,m,简单的主程序：,Fillchar(f,sizeof(f),0);,for i:=1 to n do,for j:=1 to m do,fi,j:=max(fi,j-1,fi-1,j)+ci,j;,Writeln(fn,m);,3,：简单的背包问题,(0-1,背包,),设有种物品，每种物品有一个,重量,及一个,价值,。同时有一个背包，最大载重量为,M,，今从种物品中选取若干件，使其重量的和小于等于,m,，而价值的和为最大。,N=100,M1000.,输入数据：第一行两个数：物品总数，背包载重量,M,；两个数用空格分隔；第二行,N,个数,为种物品重量,Wi(1000),；两个数用空格分隔；第三行,N,个数,为,N,种物品价值,Vi(best then best:=value;,if in then exit;/,防止溢出,dfs,(i+1,left,value);/,不装,i,if left=wi then /,装,i,dfs,(i+1,left-wi,value+vi);,end;,主程序：,init;,dfs(1,m,0);,writeln(best);,0,1,2,3,4,5,6,7,8,9,10,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,15,15,15,15,15,15,15,2,0,0,0,7,15,15,15,22,22,22,22,3,0,0,0,7,15,20,20,22,27,35,35,4,0,0,0,7,15,20,20,25,27,35,35,背包的容量,0-10,物品,0-4,编号,1,2,3,4,容量,4,3,5,7,价值,15,7,20,25,4,件物品 背包容量：,10,算法,2,：,设,fi,j:,从,1,到,i,件物品中选若取干件放到容量为,j,的背包中，获得的最大价值。目标是：,fn,m,用,fi,j,表示在第到第,i,件物品中装入重量为,j,的背包获得的最大价值,fi,j=max fi-1,j ,fi-1,j-Wi,+Vi,(1=i=n,1=j=wi,1)fi-1,j:,不放第,i,件物品获得的价值。,主程序：,fillchar(f,sizeof(f),0);,for i:=,1,to n do,for j:=1 to m do,begin,fi,j:=fi-1,j;,/,不选择第,i,件物品,if(j=wi)and(fi,jfi-1,j-wi+vi)/,选择第,i,件物品,then fi,j:=fi-1,j-wi+vi;,end;,writeln(fn,m);,end.,4,：,求最大连续子序列的和,输入：第一行：,n,（,Nans then ans:=sum;,end;,writeln(ans);,时间：,O(n,3,),理想的算法：,ans then ans:=sum;,end;,end;,writeln(ans);,时间：,O(n,2,),算法,1,和算法,2,是把,n,个数看作独立的没有联系的数来处理的。,1,、以,ai,为结束点和以,ai+1,为结束点的最大连续子序列有没有联系？,有什么样的联系？,2,、,fi,：从第,1,项开始，以,ai,为终点（右边界）的子序列的最大和。,如果事先已经求得了以,ai,为结束点的最大连续子序列和为,fi,，那么怎样求以,ai+1,为结束点的最大连续子序列？,-6 4 -1 3 2 -3 2,算法,3,：,ai:,存储序列；,fi,：从第,1,项开始，以,ai,为终点（右边界）的子序列的最大和。,fi=maxfi-1+ai,ai,：即看,fi-1,的正负,初始：,f1=a1,目标：,maxfi 1=ians then ans:=fi;,end;,时间：,O(n),在一个,nm,的方格中，,m,为奇数，放置有,nm,个数，如图,16,4,3,12,6,0,3,4,-5,6,7,0,0,2,6,0,-1,-2,3,6,8,5,3,4,0,0,-2,7,-1,7,4,0,7,-5,6,0,-1,3,4,12,4,2,人,方格中间的下方有一人，此人可按照五个方向前进但不能越出方格。,如所示：,5,取数,n,m=1)and(k+jfi,j),then fi,j:=fi+1,k+j;,fi,j:=fi,j+ai,j;,end;,ans:=f1,1;,for i:=2 to m do,if f1,ians then ans:=f1,i;,writeln(ans);,end;,6,迷宫寻宝,一个,n,行,m,列的迷宫（,1=n,m=50,），入口在左上角，规定只能向,下,或向,右,走。迷宫的某些地方藏有不同价值的宝藏，同时有存在一些障碍无法通过。求到达右下角出口时收集的宝藏的最大值。,输入：,第一行,n,和,m,，,n,行,m,列：迷宫矩阵,ai,j,（,-1,：障碍）保证,a1,1-1,。,输出：最大值。,样例：,输入,2,：,5 4,2 1 3-1,1-1-1-1,2-1 20-1,3 1 2 5,-1 1-1 2,输出,2,：,18,输入,1,：,3 4,2,-1 50 5,1,3,-1 6,-1,8 9 10,输出,1,：,33,i,j,i,j+1,i+1,j,i-1,j,i,j-1,i,j,分析：逐行扫描,ai,j,保存第,i,行第,j,列的宝藏价值,fi,j,走到第,i,行第,j,列时所能收集的宝藏的最大价值,状态转移方程：,fi,j=maxfi-1,j,fi,j-1+ai,j (1=n,1a then max:=b;end;,procedure dp;,begin,fillchar(f,sizeof(f),0);,for i:=1 to n do,for j:=1 to m do,if ai,j-1 then,fi,j:=max(fi-1,j,fi,j-1)+ai,j;,end;,？,-1,-1,20,读入数据的预处理：,if ai-1,j=-1 and ai,j-1=-1 then ai,j=-1,var,f,a:array0.maxn,0.maxmof integer;,加边界，减少判断越界,readln(n,m);,for i:=0 to n+1 do,初始全是障碍,for j:=0 to m+1 do ai,j:=-1;,a0,1:=0;,保证,a1,1,能到达,for i:=1 to n do,for j:=1 to m do,begin,read(ai,j);,if(ai,j-1=-1)and(ai-1,j=-1),then ai,j:=-1;,end;,3 4,2 -1 50 5,1 3 -1 6,-1 8 9 10,某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统（能发射任意发炮弹）。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都要求高于前一发的高度。,某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入敌国导弹依次飞来的高度（雷达给出的高度数据是不大于,30000,的正整数），计算这套系统最多能拦截多少导弹,7,、拦截导弹,输入,:,第一行：,n,（,=1000,），敌国导弹的数量。,依次是敌国导弹的高度,(30000),。,输出：,最多拦截敌国导弹的数量。,样例：,输入：,8,2 7,1,9 10,1 2 3,输出：,4,转化：,求最长的递增子序列长度。,ai:,保存数列的第,i,个数。,fi:,以,ai,为结尾,(ai,是最后一个元素,即包含,ai),的最长递增子序列的序列长度。,2 7 1 9 10 1 2 3,方法一,:,从前向后,fi=maxfj+1,条件：,1=ji,并且,ajai,边界：,f1=1;,目标：,maxfi ;1=imax then max:=fi;,writeln(max);,end.,ai:,保存数列的第,i,个数。,fi:,以,ai,为开始,(ai,是第一个元素,即包含,ai),的最长递增子序列的序列长度。,2 7 1 9 10 1 2 3,方法二：从后向前,fi=maxfj+1,条件：,ij=n,并且,aiaj,边界：,fn=1;,目标：,maxfi ;1=imax then max:=fi;,end;,怎样求最长递减子序列长度？,谢谢观看,谢谢观看,