第9讲-深搜与简单的动态规划课件.ppt

1、第第 9 讲讲 深搜与简单的动态规划深搜与简单的动态规划深度优先搜索算法的框架深度优先搜索算法的框架: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)/删除标志删除标志;恢复之前的状态恢复

2、之前的状态,根据具体情况选择根据具体情况选择:回溯回溯 end end1 1、数字三角形、数字三角形 有一个数字三角形，编程求从最顶层到最底层的一条路所经过位有一个数字三角形，编程求从最顶层到最底层的一条路所经过位置上数字之和的最大值。每一步只能向左下或右下方向走。下图数据置上数字之和的最大值。每一步只能向左下或右下方向走。下图数据的路应为的路应为7-3-8-7-57-3-8-7-5，和为，和为3030。输入：输入：第一行：第一行：R(1=R=100),R(1=R=100),数字三角形共有数字三角形共有R R行；行；以下以下R R行：依次表示数字三角形中每行中的数字。行：依次表示数字三角形中每

3、行中的数字。每个数都是非负的，且每个数都是非负的，且=100.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 44 5 2 6 5 7 3 8 8 1 0 2 7 4 44 5 2 6 5为什么当为什么当n n较大时速度慢？较大时速度慢？f:array0.100,0.100 of integer;fi,j:(i,j)到最后一行经过数的和的最大

4、值到最后一行经过数的和的最大值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:=

5、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时取得的最大值时取得的最大值根据题意可得出递推关系

6、：根据题意可得出递推关系：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：动态规划算法（效率高）。：动态规划算法（效率高）。在一个在一个n*m的棋盘内，一些格子里有垃圾要拾捡。现在的棋盘内，一些格子里有垃圾要拾捡。现在有一个能捡垃圾的机器人从左上格子里出发，每次只能向有一个能捡垃圾的机器人从左

7、上格子里出发，每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内右或者向下走。每次他到达一个点，就会自动把这个点内的垃圾拾掉。的垃圾拾掉。问：机器人到达右下角时最多能拾多少垃圾。问：机器人到达右下角时最多能拾多少垃圾。数据范围数据范围:n=100,mans 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算法算法2:因为只能向右或者向下走。也就是说不能走回头路。因为只能向右或者向下走。也就是说不能走回头路。

8、设设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 3：

9、简单的背包问题：简单的背包问题(0-1(0-1背包背包)设有种物品，每种物品有一个设有种物品，每种物品有一个重量重量及一个及一个价值价值。同时有一。同时有一个背包，最大载重量为个背包，最大载重量为M M，今从种物品中选取若干件，使其重量，今从种物品中选取若干件，使其重量的和小于等于的和小于等于m m，而价值的和为最大。，而价值的和为最大。N=100,M1000.N=100,M1000.输入数据：输入数据：第一行两个数：物品总数，背包载重量第一行两个数：物品总数，背包载重量M M；两个数用空格分隔；两个数用空格分隔；第二行第二行N N个数个数,为种物品重量为种物品重量WiWi(1000)(100

10、0)；两个数用空格分隔；两个数用空格分隔；第三行第三行N N个数个数,为为N N种物品价值种物品价值Vi(1000);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);01234567891000000000000010000151515151515152000715151522222222300071520202

11、22735354000715202025273535背包的容量背包的容量0-10物品物品0-4编号编号1234容量容量4357价值价值15720254件物品件物品 背包容量：背包容量：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=wi1)fi-1,j:不放第不放第i件物品

12、获得的价值。件物品获得的价值。主程序：主程序：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 4：求最大连续子序列的和求最大连续子序列的和输入：第一行：输入：第一行：n（Nans then ans:=sum;end;writeln(ans);时间：时间：O(n3)理想的算法：

13、理想的算法：ans then ans:=sum;end;end;writeln(ans);时间：时间：O(n2)算法算法1和算法和算法2是把是把n个数看作独立的没个数看作独立的没有联系的数来处理的。有联系的数来处理的。1、以、以ai为结束点和以为结束点和以ai+1为结束点的最大连续为结束点的最大连续子序列有没有联系？子序列有没有联系？有什么样的联系？有什么样的联系？2、fi：从第：从第1项开始，以项开始，以ai为终点（右边界）的子序为终点（右边界）的子序列的最大和。列的最大和。如果事先已经求得了以如果事先已经求得了以ai为结束点的最大连续子序列和为结束点的最大连续子序列和为为fi，那么怎样求以

14、，那么怎样求以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个数，如图个数，如图 1643126034-56700260-1-236853400-27-1740

15、7-560-1341242人方格中间的下方有一人，此人可按照五个方向前进但不能越出方格。方格中间的下方有一人，此人可按照五个方向前进但不能越出方格。如所示：如所示：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），入口在左上角，），入口在左上角，规定只能向规定只能向下下或向或向右右走。迷宫的某些地方藏有不

16、同价值走。迷宫的某些地方藏有不同价值的宝藏，同时有存在一些障碍无法通过。求到达右下角的宝藏，同时有存在一些障碍无法通过。求到达右下角出口时收集的宝藏的最大值。出口时收集的宝藏的最大值。输入：输入：第一行第一行n和和m，n行行m列：迷宫矩阵列：迷宫矩阵ai,j（-1：障碍）保证：障碍）保证a1,1-1。输出：最大值。输出：最大值。样例：样例：输入输入2：5 42 1 3-11-1-1-12-1 20-13 1 2 5-1 1-1 2输出输出2：18输入输入1：3 42 -1 50 51 3 -1 6-1 8 9 10输出输出1：33i,ji,j+1i+1,ji-1,ji,j-1i,j分析：逐行扫

17、描分析：逐行扫描ai,j 保存第保存第i行第行第j列的宝藏价值列的宝藏价值fi,j走到第走到第i行第行第j列时所能收集的宝藏的最大价值列时所能收集的宝藏的最大价值状态转移方程：状态转移方程：fi,j=maxfi-1,j,fi,j-1+ai,j (1=n,1=m)条件条件:ai,j-1时时.初始：初始：f1,1=a1,1;目标：目标：fn,mfunction max(a,b:integer):integer;begin max:=a;if ba then max:=b;end;procedure dp;begin fillchar(f,sizeof(f),0);for i:=1 to n do

18、for j:=1 to m do if ai,j-1 then fi,j:=max(fi-1,j,fi,j-1)+ai,j;end;？-1-120读入数据的预处理：读入数据的预处理：if ai-1,j=-1 and ai,j-1=-1 then ai,j=-1var 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

19、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 42 -1 50 51 3 -1 6-1 8 9 10 某国为了防御敌国的导弹袭击，发展出一种导弹拦截某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统（能发射任意发炮弹）。但是这种导弹拦截系统有一系统（能发射任意发炮弹）。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都要求高于前一发的高度。以后每一发炮弹都要求高于前一发的高度。某天，雷达捕捉

20、到敌国的导弹来袭。由于该系统还在某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。的导弹。输入敌国导弹依次飞来的高度（雷达给出的高度数据输入敌国导弹依次飞来的高度（雷达给出的高度数据是不大于是不大于30000 的正整数），计算这套系统最多能拦截多的正整数），计算这套系统最多能拦截多少导弹少导弹 7、拦截导弹、拦截导弹 输入输入:第一行：第一行：n（=1000），敌国导弹的数量。），敌国导弹的数量。依次是敌国导弹的高度依次是敌国导弹的高度(30000)。输出：输出：最多拦截敌国导弹的数量。最多

21、拦截敌国导弹的数量。样例：样例：输入：输入：82 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=i=n输入：输入：82 7 1 9 10 1 2 3输出：输出：4fi:1 2 1 3 4 1

22、2 3 f1:=1;for i:=2 to n do begin fi:=0;for j:=1 to i-1 do if(ajfi)then fi:=fj;找最大的找最大的fj fi:=fi+1;包括包括ai end;max:=f1;For i:=2 to n do if fimax then max:=fi;writeln(max);end.ai:保存数列的第保存数列的第i个数。个数。fi:以以ai为开始为开始(ai是第一个元素是第一个元素,即包含即包含ai)的最长递的最长递增子序列的序列长度。增子序列的序列长度。2 7 1 9 10 1 2 3方法二：从后向前方法二：从后向前fi=maxf

23、j+1 条件：条件：ij=n并且并且aiaj边界：边界：fn=1;目标：目标：maxfi ;1=i=n fn fn:=1;max:=fn;:=1;max:=fn;for i:=n-1 downto for i:=n-1 downto 1 do 1 do begin begin fi fi:=0;:=0;for j:=i+1 to n do for j:=i+1 to n do if(bifi)then fi:=fj;if(bifi)then fi:=fj;inc(fi inc(fi););if fimax then max:=fi;if fimax then max:=fi;end;end;怎样求最长递减子序列长度？怎样求最长递减子序列长度？