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

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) / 删除标志;恢复之前的状态,根据具体情况选择: 回溯 end end1、数字三角形 有一个数字三角形，编程求从最顶层到最底层的一条路所经过位置上数字之和的最大值。每一步只能向左下或右下

2、方向走。下图数据的路应为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 44 5 2 6 5 7 3 8 8 1 0 2 7 4 44 5 2 6 5为什么当n较大时速度慢？f:array0.100,0.100 of

3、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,

4、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

5、初始：f1,1:=a1,1;目标：maxfn,i 1=ians then ans:=fn,i; writeln(ans); end;总结：算法1：一般的搜索（效率很低）。算法2：记忆化搜索（效率高）。算法3和算法4：动态规划算法（效率高）。 在一个n*m的棋盘内，一些格子里有垃圾要拾捡。现在有一个能捡垃圾的机器人从左上格子里出发，每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内的垃圾拾掉。问：机器人到达右下角时最多能拾多少垃圾。数据范围:n=100,mans then ans:=sum; if in then dfs(i+1,j,sum+ci+1,j); if jm then df

6、s(i,j+1,sum+ci,j+1); end;初始：dfs(1,1,ci,j)结果是：ans算法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,

7、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+

8、1,left-wi,value+vi); end;主程序： init; dfs(1,m,0); writeln(best);0123456789100000000000001000015151515151515200071515152222222230007152020222735354000715202025273535背包的容量0-10物品0-4编号1234容量4357价值15720254件物品 背包容量：10算法2：设fi,j:从1到i件物品中选若取干件放到容量为j的背包中，获得的最大价值。目标是：fn,m用fi,j表示在第到第i件物品中装入重量为j的背包获得的最大价值fi,j=max

9、fi-1,j , fi-1,j-Wi+Vi (1=i=n,1=j=wi1) 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);

10、时间：O(n3)理想的算法：ans then ans:=sum; end; end; writeln(ans); 时间：O(n2)算法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

11、-1的正负初始：f1=a1目标：maxfi 1=ians then ans:=fi; end;时间：O(n)在一个nm的方格中，m为奇数，放置有nm个数，如图 1643126034-56700260-1-236853400-27-17407-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

12、); end;6 迷宫寻宝一个n行m列的迷宫（1=n,m=50），入口在左上角，规定只能向下或向右走。迷宫的某些地方藏有不同价值的宝藏，同时有存在一些障碍无法通过。求到达右下角出口时收集的宝藏的最大值。输入：第一行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分析：逐行扫描ai,j 保存第i行第j列的宝藏价值fi,

13、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 for j:=1 to m do if ai,j-1 then fi,j:=max(fi-1,j,fi,j-1)+ai,j; end;？

14、-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 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

15、 50 51 3 -1 6-1 8 9 10 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统（能发射任意发炮弹）。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都要求高于前一发的高度。 某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入敌国导弹依次飞来的高度（雷达给出的高度数据是不大于30000 的正整数），计算这套系统最多能拦截多少导弹 7、拦截导弹 输入: 第一行：n（=1000），敌国导弹的数量。 依次是敌国导弹的高度(30000)。输出： 最多拦截敌国导弹的数量。样例：输入：82 7

16、 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 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个