算法设计技巧与分析

1、2022/4/10 linzhenjie12022/4/10 linzhenjie2 贪心算法总是作出在当前看来最好的选择，也就贪心算法总是作出在当前看来最好的选择，也就是说贪心算法并不从整体最优考虑，它所作出的是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的选择只是在某种意义上的局部最优局部最优选择。选择。 贪心算法不能对所有问题都得到整体最优解，但贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整

2、体最优解，其最终结果却使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。是最优解的很好近似。2022/4/10 linzhenjie3 贪心算法通常用于求解最优化问题，即量的最大化或最小贪心算法通常用于求解最优化问题，即量的最大化或最小化问题。算法每一步工作较少且基于信息，因此特别有效。化问题。算法每一步工作较少且基于信息，因此特别有效。 贪心算法通常包含一个用以寻找局部最优解的迭代过程。贪心算法通常包含一个用以寻找局部最优解的迭代过程。其在少量计算的基础上做出了正确猜想而且不考虑以后情其在少量计算的基础上做出了正确猜想而且不考虑以后情况，一步步来构筑解，每一次均建立在局部最优解的

3、基础况，一步步来构筑解，每一次均建立在局部最优解的基础上。每一步同时又扩大了部分解的规模，做出的选择产生上。每一步同时又扩大了部分解的规模，做出的选择产生最大的直接收益而又保持可行性。最大的直接收益而又保持可行性。 算法缺陷在于要证明该算法确实是求解了要解决的问题。算法缺陷在于要证明该算法确实是求解了要解决的问题。2022/4/10 linzhenjie4 活动安排问题活动安排问题活动安排问题是可以用贪心算法有效求解的活动安排问题是可以用贪心算法有效求解的一个很好的例子。该问题要求高效地安排一系列一个很好的例子。该问题要求高效地安排一系列争用某一公共资源的活动。争用某一公共资源的活动。 贪心算

4、法提供了一个简单、贪心算法提供了一个简单、 漂亮的方法使得尽可能多漂亮的方法使得尽可能多 的活动能兼容地使用公共的活动能兼容地使用公共 资源。资源。 贪心算法特性：贪心算法特性：由一个简单的迭代过程由一个简单的迭代过程构成，在维持可行性的构成，在维持可行性的前提下选择产生最大直前提下选择产生最大直接利益的项。接利益的项。2022/4/10 linzhenjie5 设有设有n个活动的集合个活动的集合e=1，2，n，其中每个，其中每个活动都要求使用同一资源，如演讲会场等，而在活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个同一时间内只有一个活动能使用这一资源。每

5、个活动活动i都有一个要求使用该资源的起始时间都有一个要求使用该资源的起始时间si和一和一个结束时间个结束时间fi,且且sifi。如果选择了活动。如果选择了活动i，则它在，则它在半开时间区间半开时间区间si，fi内占用资源。若区间内占用资源。若区间si，fi与区间与区间sj，fj不相交，则称活动不相交，则称活动i与活动与活动j是相容是相容的。也就是说，当的。也就是说，当sifi或或sjfj时，活动时，活动i与活动与活动j相相容。活动安排问题就是要在所给的活动集合中选容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。出最大的相容活动子集合。 2022/4/10 linzhenjie

6、6 在下面所给出的解活动安排问题的贪心算法在下面所给出的解活动安排问题的贪心算法中，各活动的起始时间和结束时间存储中，各活动的起始时间和结束时间存储于数组于数组s和和f中且按结束时间的非减序：中且按结束时间的非减序：. f1f2 fn排列。排列。如果所给出的活动未按此序排列，如果所给出的活动未按此序排列，我们可以用我们可以用o(nlogn)的时间将它重排。的时间将它重排。 2022/4/10 linzhenjie7 活动安排问题活动安排问题int schedule(int s,int f,bool a,int r)int n=1;int j=0;a0=true;for(int i=1;i=fj

7、)ai=true;n+;j=i;elseai=false;coutthe least amount meeting place is :n;return n;2022/4/10 linzhenjie9 算法算法中用集合中用集合 来存储所选择的活动。来存储所选择的活动。活动活动i在集合在集合a中，当且仅当中，当且仅当ai的值为的值为true。变量。变量 n用以记录最近一次加入到用以记录最近一次加入到a中的活动。中的活动。 贪心算法贪心算法一开始选择活动一开始选择活动1，并将，并将n初始初始化为化为1。然后依次检查活动。然后依次检查活动i是否与当前已选择的是否与当前已选择的所有活动相容。若相容则将

8、活动所有活动相容。若相容则将活动i加人到已选择活加人到已选择活动的集合动的集合a中，否则不选择活动中，否则不选择活动i，而继续检查下，而继续检查下一活动与集合一活动与集合a中活动的相容性。中活动的相容性。 2022/4/10 linzhenjie10 完整程序完整程序 #include using namespace std; void sort(int f,int n) int temp; for(int i=1;in;i+) for(int j=0;jfj+1) temp=fj; fj=fj+1; fj+1=temp;coutthe sort result:endl;for( i=0;in

9、;i+) coutfi,;coutendl;2022/4/10 linzhenjie12int schedule(int s,int f,bool a,int r) int n=1; int j=0; a0=true; for(int i=1;i=fj) ai=true;n+;j=i; else ai=false; coutthe least amount meeting place is :n;2022/4/10 linzhenjie13 return n; void main() int r;/活动数活动数 int p=0; coutplease input the activity quantityr; coutplease input the start_timeendl; int *st=new intr+1; bool *a=new boolr+1; for(int i=0;isti;2022/4/10 linzhenjie14coutplease inputthe end_timeendl;int *et=n