基础算法枚举贪心分治策略.ppt

基础算法策略第一部分枚举策略的基本思想枚举策略的基本思想虽然枚举法本质上属于搜索策略，但是它与回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件：⑴可预先确定每个状态的元素个数n；
⑵状态元素a1，a2，…，an的可能值为一个连续的值域。
设
ai1—状态元素ai的最小值；aik—状态元素ai的最大值(1≤i≤n)，即a11≤a1≤a1k，a21≤a2≤a2k，ai1≤ai≤aik，……，an1≤an≤ank
fora1←a11toa1kdo
foa2←a21toa2kdo……………………
forai←ai1toaikdo……………………
foran←an1toankdo
if状态(a1，…，ai，…，an)满足检验条件
then输出问题的解；
枚举策略的基本思想枚举方法的优化枚举算法的应用【分析】此题是一道统计类题目。解决统计问题的一个常用方法是枚举法：逐一枚举所有情况，同时进行统计，枚举结束时，统计也完成，得到结果。
具体对本题而言，采用枚举法的正确性与可行性是显然的，而本题的数据规模又仅为1～1000，所以采用逐一枚举方法进行统计的时间复杂度是完全可以接受的。例题2：01统计例题4：圆桌骑士（IOI试题）
在一个8*8的棋盘上，有一个国王和若干个武士。其中，国王走一字步，骑士走马步。若国王与骑士相会在同一点上，国王可以选择让骑士背他走。求一个点，使所有的骑士和国王相距在这个点上的所走的步数最少。【分析】此题可从3个方面考虑：
分治、枚举、数学方法。
由于无法将这个问题划分为各自独立的小问题来解决，分治显然是不行的。又因武士和国王位置的不固定性和其走法的差异，推导不出一个数学公式。因此考虑使用枚举，需要枚举的三个要点：
1、最后的汇聚点。
2、国王与背他的骑士的汇聚点。
3、国王与背他的骑士。国王最多只会与一个骑士结合，因为骑士的最终目标也是最终汇聚点，一旦国王与某个骑士汇合后，即马上可与其结合，剩下的只需要将所有的骑士汇合就可以了。更没有必要在中途中有将国王托付给其他的骑士。这样我们估算一下时间为O（8*8*8*8*63）=O（36*10^4），完全可以承受。
另外，我们需要预先将2点之间走马字步的距离计算出来。可以使用Floyd或是Bfs。算法流程：

dis[x1，y1，x2，y2]--（x1，y1）（x2，y2）之间的距离。
ForI：=1to8do{枚举汇合点}
Forj：=1to8dobegin
All：=所有骑士到这一点的和；
Best:=min(best,all+国王到汇聚点的步数)
Forx：=1to8do{枚举武士国王的相会点}
Fory：=1to8dobegin
Forkk：=1tokdo{枚举与国王结合的武士}
Ifdis[knight[kk].x,knight[kk].y,x,y]<minthenbegin
Min:=dis[knight[kk].x,knight[kk].y,x,y];
Mink:=k;
End;
End；
Now:=all-mink武士走到汇合点的距离+mink武士走到汇聚点的距离+国王走到汇聚点的距离+从汇聚点到汇合点的距离；
Best：=min（best，now）
End；局部枚举局部枚举分析最大子矩阵的求解方法第二部分贪心方法的基本思想适用于贪心策略求解的问题的特点贪心方法的应用贪心方法的应用贪心方法的应用贪心方法的应用贪心方法的应用贪心方法的应用贪心方法的应用贪心方法的应用贪心方法的应用贪心方法的应用贪心方法的应用贪心方法的应用贪心方法的应用贪心方法的应用贪心方法的应用贪心方法的应用贪心方法的应用贪心方法的应用贪心方法的应用贪心方法的应用贪心方法的应用贪心方法的应用贪心方法的推广贪心与其它算法结合贪心与其它算法结合贪心与其它算法结合贪心方法小结第三部分归纳法的基本思想归纳法解题的过程归纳法解题的过程归纳策略解题应注意的问题：归纳策略的应用归纳策略的应用归纳策略的应用归纳策略的应用归纳策略的应用归纳策略的应用归纳策略的应用【算法描述】
m←k；
whilem≥idobegin
求△1
if△1为整数thenbegin
求n1；
if(n1为整数)and(n1≤k)
Thenbegin输出m和n1；halt;end
end;｛then｝
求△2；
if△2为整数thenbegin
求n2；
if（n2为整数）and（n2≤k）
thenbegin输出m和n2;halt;end
end;{then}
m←m－l;
end;{while}归纳策略的应用归纳策略的应用归纳策略的应用归纳策略的应用归纳策略的应用归纳策略的应用归纳策略的应用归纳策略的应用归纳策略的应用归纳策略的应用归纳策略的应用第四部分递归的概念与应用递归的概念与应用递归的概念与应用递归的概念与应用递