深搜及优化重点.ppt

回 溯 法 回溯法主要是对每种可能的路径进行试探，直到到达到目标或所有的可能性都试探完毕为止。回溯法是有哪些信誉好的足球投注网站算法中的一种控制策略，也是求解特殊型计数题或较复杂的枚举题中使用频率最高的一种算法。 典型例题 N皇后问题 背包问题 寻找国都名 …… 回溯法的算法框架 Procedure run(当前状态)； Var i:integer; Begin if 当前状态为边界 then begin if 当前状态为最佳目标状态 then 记下最优结果； exit; {回溯} end; for i:=最小值 to 最大值 do begin 算符i作用于当前状态，扩展出一个子状态； if (子状态满足约束条件) and (子状态满足最优性要求) then run(子状态)； end; End; 0,1背包问题 已知一个容量大小为M重量的背包和N种物品，每种物品的重量为Wi，价值为Pi，要求从N件物品中任取若干件（可以一件也不取，也可以全取），使得重量之和≤M，而价值之和为最大。 【输入格式】 第一行是两个正整数M，N; 以下N行，每行两个正整数Wi，Pi 【输出格式】 一个数，表示满足题目要求的价值之和的最大值。 0,1背包问题 【输入样例】 100 5 77 92 22 22 29 87 50 46 99 90 【输出样例】 133 算法分析 本题可以用递归求解：设当前有N个物品，容量为M；因为这些物品要么选，要么不选，我们假设选的第一个物品编号为i（1~i-1号物品不选），问题又可以转化为有N-i个物品（即第i+1~N号物品），容量为M-Wi的子问题……如此反复下去，然后在所有可行解中选一个效益最大的便可。 算法框架 Procedure Search(I:Integer; J:Byte); {递归求解} Var K :Byte; Begin If NowAns Then Begin {修改最优解} Ans:=Now; Pr:=Ou; End; For K:=J To N Do {选取物品} If W[K]=I Then Begin Now:=Now+P[K]; Ou[K]:=True; Search(I-W[K],K+1); Now:=Now-P[K]; Ou[K]:=False; End; End; var m,n,now,ans:integer; w,p:array[1..100] of integer; ou,pr:array[1..100] of boolean; i:integer; procedure init; begin readln(m,n); for i:=1 to n do readln(w[i],p[i]); end; begin init; fillchar(ou,sizeof(ou),false); now:=0; ans:=0; search(m,1); writeln(ans); for i:=1 to n do if pr[i] then write(i, ); writeln; end. 一个简单的优化： 我们定义一个函数如下： F[i]表示选第I~N个物品能得到的总效益。不难推出： F[N]=Pn F[i]=F[i+1]+Pi （i=1…N-1） 假设当前已选到第i号物品，如果当前有哪些信誉好的足球投注网站的效益值+F[i+1]的值仍然比当前的最优值小，则没有必要继续有哪些信誉好的足球投注网站下去。 算法框架 Procedure Search(I:Integer; J:Byte); {递归求解} Var K :Byte; Begin If Now+F[J]=Ans Then Exit; {如果没有必要有哪些信誉好的足球投注网站下去} If NowAns Then Begin {修改最优解} Ans:=Now; Pr:=Ou; End; For K:=J To N Do {选取物品} If W[K]=I Then Begin Now:=Now+P[K]; Ou[K]:=True; Search(I-W[K],K+1); Now:=Now-P[K]; Ou[K]:=False; End; End; var m,n,now,ans:integer; f,w,p:array[1..100] of integer; ou,pr:a