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

第 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 end,1、数字三角形 有一个数字三角形，编程求从最顶层到最底层的一条路所经过位置上数字之和的最大值。每一步只能向左下或右下方向走。下图数据的路应为7-3-8-7-5，和为30。输入：第一行：R(1=R=100),数字三角形共有R行；以下R行：依次表示数字三角形中每行中的数字。每个数都是非负的，且=100.输出：一个正整数，路径上数字之和的最大值。输入样例：573 88 1 02 7 4 44 5 2 6 5输出样例：30,7 3 8 8 1 0 2 7 4 44 5 2 6 5,算法1：深度优先搜索算法DFS：,二维数组ai，j存储数字三角形。Procedure dfs(sum,i,j:integer);/从a1,1到走到第i行第j列即ai,j时所取得的值为sum begin if i=n then begin if summax 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 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=i=n目标：f1,1,算法3：,7 3 8 8 1 0 2 7 4 44 5 2 6 5,procedure main;begin for i:=1 to n do fn,i:=an,i;for i:=n-1 downto 1 do 枚举行 for j:=1 to i do 枚举每行的元素 fi,j:=max(fi+1,j,fi+1,j+1)+aI,j;枚举走法 writeln(f1,1);end;,function max(a,b:integer):integer;begin max:=a;if bmax 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=i=n,7 3 8 8 1 0 2 7 4 44 5 2 6 5,算法4：,procedure main;顺推 begin f1,1:=a1,1;for i:=2 to n do for j:=1 to i do fi,j:=max(fi-1,j-1,fi-1,j)+ai,j;ans:=fn,1;for i:=2 to n do if fn,ians then ans:=fn,i;writeln(ans);end;,总结：,算法1：一般的搜索（效率很低）。算法2：记忆化搜索（效率高）。算法3和算法4：动态规划算法（效率高）。,在一个n*m的棋盘内，一些格子里有垃圾要拾捡。现在有一个能捡垃圾的机器人从左上格子里出发，每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内的垃圾拾掉。问：机器人到达右下角时最多能拾多少垃圾。数据范围:n=100,m=100,2、Robots 机器人捡垃圾,样例输入：6 771 21 42 42 64 44 76 6,样例输出：5,算法1：dfs,Ci,j=1表示(i,j)点有垃圾。Ci,j=0表示没有。procedure dfs(i,j,sum:longint);/从(i,j)走到终点(n,m)能捡到的垃圾数是sum begin if(i=n)and(j=m)then if sumans 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:,因为只能向右或者向下走。也就是说不能走回头路。设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(1000);两个数用空格分隔；输出数据：总价值；,输入样例1：4 104 3 5 715 7 20 25输出样例1：35,输入样例2：4 202 9 10 15 2 9 10 16 输出样例2：19,Dfs算法:,const maxn=100;var n,m:integer;/n：物品数量；m：背包容量 w:array1.maxn of integer;/物品重量 v:array1.maxn of integer;/物品价值 best:longint;/最大价值,procedure dfs(i,left,value:longint);/i：搜索第i件物品:判断放还是不放到背包里/left：背包的剩余空间/value：已装物品的价值 begin if i=n+1 then if valuebest 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-10,物品0-4,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=m),目标：fn,m;,2)fi-1,j-Wi+Vi：放第i件的价值。条件：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（N10000）第二行：n个整数（-3000，3000）。输出：最大连续子序列的和。样例：输入：7-6 4-1 3 2-3 2输出：8,算法1：枚举任意连续区间求和找最大值,readln(n);for i:=1 to n do read(ai);ans:=-30000000;for i:=1 to n do for j:=i to n do begin sum:=0;for k:=i to j do sum:=sum+ak;if sumans then ans:=sum;end;writeln(ans);,时间：O(n3)理想的算法：=106,算法2：算法1的优化,readln(n);for i:=1 to n do read(ai);ans:=-30000000;for i:=1 to n do begin sum:=0;for j:=i to n do begin sum:=sum+aj;if sumans 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-1的正负初始：f1=a1目标：maxfi 1=i=n,procedure dp;begin f1:=a1;for i:=2 to n do fi:=max(fi-1+ai,ai);ans:=f1;for i:=2 to n do if fians then ans:=fi;end;,时间：O(n),在一个nm的方格中，m为奇数，放置有nm个数，如图,方格中间的下方有一人，此人可按照五个方向前进但不能越出方格。如所示：,5 取数,n,m=100,方格数-100，100,样例输入：6 716 4 3 12 6 0 34-5 6 7 0 0 26 0-1-2 3 6 85 3 4 0 0-2 7-1 7 4 0 7-5 60-1 3 4 12 4 2,样例输出：51,fi,j:人走到（i，j）时得数的最大值。,fi,j=maxfi+1,j-2,fi+1,j-1,fi+1,j,fi+1,j+1,fi+1,j+2+ai,j,procedure dp;begin k:=m div 2+1;for i:=k-2 to k+2 do fn,i:=an,i;for i:=n-1 downto 1 do for j:=max(1,k-2*i)to min(k+2*i,m)do begin fi,j:=-10001;for k:=-2 to 2 do if(k+j=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-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：33,分析：逐行扫描ai,j 保存第i行第j列的宝藏价值fi,j走到第i行第j列时所能收集的宝藏的最大价值状态转移方程：fi,j=maxfi-1,j,fi,j-1+ai,j(1-1时.初始：f1,1=a1,1;目标：fn,m,function 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;,？,读入数据的预处理：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 50 51 3-1 6-1 8 9 10,某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统（能发射任意发炮弹）。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都要求高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入敌国导弹依次飞来的高度（雷达给出的高度数据是不大于30000 的正整数），计算这套系统最多能拦截多少导弹,7、拦截导弹,输入:第一行：n（=1000），敌国导弹的数量。依次是敌国导弹的高度(30000)。输出：最多拦截敌国导弹的数量。,样例：输入：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 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=maxfj+1 条件：ij=n并且aiaj边界：fn=1;目标：maxfi;1=i=n,fn:=1;max:=fn;for i:=n-1 downto 1 do begin fi:=0;for j:=i+1 to n do if(bifi)then fi:=fj;inc(fi);if fimax then max:=fi;end;,怎样求最长递减子序列长度？,