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

第 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 算法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 f[i,j]:=a[i,j]; exit; end; if f[i,j]0 then exit; dfs(i+1,j); dfs(i+1,j+1); f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j]; end; Begin init; fillchar(f,sizeof(f),0); dfs(1,1); writeln(f[1,1]); End. 总结： 算法1：一般的有哪些信誉好的足球投注网站（效率很低）。 算法2：记忆化有哪些信誉好的足球投注网站（效率高）。 算法3和算法4：动态规划算法（效率高）。 在一个n*m的棋盘内，一些格子里有垃圾要拾捡。现在有一个能捡垃圾的机器人从左上格子里出发，每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内的垃圾拾掉。 问：机器人到达右下角时最多能拾多少垃圾。 数据范围:n=100,m=100 算法1：dfs C[i,j]=1表示(i,j)点有垃圾。C[i,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+c[i+1,j]); if jm then dfs(i,j+1,sum+c[i,j+1]); end; 算法2: 因为只能向右或者向下走。也就是说不能走回头路。 设f[i,j]表示从(1,1)点开始走到(i,j)的时候，最多捡了多少垃圾。 简单的主程序： Fillchar(f,sizeof(f),0); for i:=1 to n do for j:=1 to m do f[i,j]:=max(f[i,j-1],f[i-1,j])+c[i,j]; Writeln(f[n,m]); Dfs算法: const maxn=100; var n,m:integer; //n：物品数量；m：背包容量 w:array[1..maxn] of integer; //物品重量 v:array[1..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=w[i] then //装i dfs(i+1,left-w[i],value+v[i]); end; 主程序： init; dfs(1,m,0); writeln(best); 主程序： fillchar