算法设计与分析贪心策略提纲提纲知识点活动安排问题活动安排问题数据的预处理PublicstaticintgreedySelector(int[]s,int[]f,booleana[]){intn=s.length-1;a[1]=true;intj=1;intcount=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){a[i]=true;j=i;count++;}elsea[i]=false;}returncount;}看个例子先第一步：选择活动1作为第一个被选中的活动，并将活动1的结束时间作为判断下一个活动是否被选中的依据；第二步：判断活动2与活动1是否相容即s[2]是否大于或等于f[1]；第三步：判断活动3与活动1是否相容即s[3]是否大于或等于f[1]；第四步：判断活动4与活动1是否相容即s[4]是否大于或等于f[1]；第五步：判断活动5与活动4是否相容即s[5]是否大于或等于f[4]；第六步：判断活动6与活动4是否相容即s[6]是否大于或等于f[4]；第七步：判断活动7与活动4是否相容即s[7]是否大于或等于f[4]；第八步：判断活动8与活动4是否相容即s[8]是否大于或等于f[4]；第九步：判断活动9与活动8是否相容即s[9]是否大于或等于f[8]；第十步：判断活动10与活动8是否相容即s[10]是否大于或等于f[8]；第十一步：判断活动11与活动8是否相容即s[11]是否大于或等于f[8]；最终结果第1、4、8、11个活动被选中贪心算法解活动安排问题的分析分析分析知识点问题贪心算法的基本要素贪心选择性质贪心选择性质的确定贪心算法的基本要素最优子结构性质贪心算法的基本要素区别0-1背包问题和背包问题0-1背包问题的形式化描述背包问题的形式化描述问题分析用贪婪算法求解背包问题考虑这个问题举例分析求解原因分析提纲实例分析装船问题装船问题装船问题的形式化描述贪心策略的确定策略1下的贪心选择性质分析策略1下的贪心选择性质分析策略2下的贪心选择性质分析策略2下的贪心选择性质分析策略1下最优子结构性质算法复杂性分析哈夫曼编码哈夫曼编码实例说明符号概率编码A0.450B0.13101C0.12100D0.16111E0.091101F0.051000哈夫曼编码需要解决的两个问题前缀码前缀码的数据结构最优前缀码哈夫曼树构造哈夫曼树贪心选择策略算法复杂性分析哈夫曼编码的正确性贪心选择性质贪心选择性质证明贪心选择性质证明贪心选择性质证明——编码树的变换贪心选择性质证明贪心选择性质证明最优子结构性质最优子结构性质证明最优子结构性质证明Huffman编码的效率问题实例说明单源最短路径单源最短路径Dijkstra算法集合S的构造Dijkstra算法实现Publicstaticvoiddijkstra(intv,float[][]dist,int[]prev){intn=dist.length.-1;if(v<1||v>n)return;boolean[]s=newboolean[n+1];for(inti=1;i<=n;i++){dist[i]=a[v][i];s[i]=false;if(dist[i]==设定的大数)prev[i]=0;elseprev[i]=v;}dist[v]=0;s[v]=true;for(inti=1;i<n;i++){floattemp=设定的大数；intu=v;for(intj=1;j<=n;j++)if((!s[j])&&(dist[j]<temp)){u=j;temp=dist[j];}s[u]=true;for(intj=1;j<=n;j++)if((!s[j])&&(a[u][j]<设定的大数)){floatnewdist=dist[u]+a[u][j];if(newdist<dist[j]{dist[j]=newdist;//dist[j]减少prev[j]=u;}}}}最短路径求解实例说明实例说明实例说明实例说明实例说明最短路径求解顶点１到５的最短路径求解Dijkstra算法的贪心选择性质贪心选择性质证明贪心选择性质证明Dijkstra算法的最优子结构性质最优子结构性质证明最优子结构性质证明最优子结构性质证明Dijkstra算法的算法复杂性分析最小生成树最小生成树问题基于贪心策略的算法设计最小生成树性质MST性质证明ＭＳＴ性质证明Prim算法K