深搜与简单的动态规划

《深搜与简单的动态规划》由会员分享，可在线阅读，更多相关《深搜与简单的动态规划（48页珍藏版）》请在金锄头文库上搜索。

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 end,1、数字三角形 有一个数字三角形，编程求从最顶层到最底层的一条路所经过位置上数字之和的最大值。每一步只能向左下

2、或右下方向走。下图数据的路应为7-3-8-7-5，和为30。 输入： 第一行：R(1=R=100),数字三角形共有R行； 以下R行：依次表示数字三角形中每行中的数字。 每个数都是非负的，且=100. 输出：一个正整数，路径上数字之和的最大值。 输入样例： 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输出样例： 30,7 3 8 8 1 0 2 7 4 4 4 5 2 6 5,算法1：深度优先搜索算法DFS：,二维数组ai，j存储数字三角形。 Procedure dfs(sum,i,j:integer); /从a1,1到走到第i行第j列即ai,j时所取得的值为sum begi

3、n 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 4 4 5 2 6 5,7 3 8 8 1 0 2 7 4 4 4 5 2 6 5,为什么当n较大时速度慢？,f:array0100,0100 of integer; fi,j : (i,j) 到最后一行经过数的和的最大值,fi,j:=max(fi+1,j,fi

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

5、 init; fillchar(f,sizeof(f),0); dfs(1,1); writeln(f1,1); End.,设fi,j:ai,j到达第n行an,k（k：1n）的最大值 递推关系：,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 4 4 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:=

6、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 4 4 5 2 6 5,算法4：,procedure mai

7、n;顺推 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的棋盘内，一些格子里有垃圾要拾捡。现在有一个能捡垃圾的机器人从左上格子里出发，每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内的垃圾

8、拾掉。 问：机器人到达右下角时最多能拾多少垃圾。 数据范围:n=100,m=100,2、 Robots 机器人捡垃圾,样例输入： 6 7 7 1 2 1 4 2 4 2 6 4 4 4 7 6 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 t

9、hen 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,

10、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 10 4 3 5 7 15 7 20 25 输出样例1： 35,输入样例

11、2： 4 20 2 9 10 15 2 9 10 16 输出样例2： 19,Dfs算法:,const maxn=100; var n,m:integer; /n：物品数量；m：背包容量 w:array1maxn of integer; /物品重量 v:array1maxn of integer; /物品价值 best:longint; /最大价值,procedure dfs(i,left,value:longint); /i：搜索第i件物品:判断放还是不放到背包里 / left：背包的剩余空间 / value：已装物品的价值 begin if i=n+1 then if valuebest t

12、hen 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

13、 (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） 第二行：

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

15、; 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;