文档介绍：贪心算法 1贪心算法基本思想 2典型贪心算法 3哈夫曼树 4最小生成树贪心算法 1贪心算法的基本思想贪心法在解决问题的策略上目光短浅,只根据当前已有的信息就做出选择,而且一旦做出了选择,不管将来有什么结果,这个选择都不会改变。从问题的某一个初始解出发逐步逼近给定的目标,每一步都作一个不可回溯的决策,尽可能地求得最好的解。当达到某算法中的某一步不需要再继续前进时,算法停止。换言之,贪心法并不是从整体最优考虑,它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总能获得整体最优解但通常能获得近似最优解。该算法适用的问题: 贪婪算法对问题只需考虑当前局部信息就要做出决策,也就是说使用贪婪算法的前提是“局部最优策略能导致产生全局最优解”。该算法的适用范围较小, 若应用不当, 不能保证求得问题的最佳解。一般情况下通过一些实际的数据例子, 就能从直观上就能判断一个问题是否可以用贪婪算法。更准确的方法是通过数学方法证明问题对贪婪策略的选用性。 1、币种统计问题某单位给每个职工发工资(精确到元)。为了保证不要临时兑换零钱, 且取款的张数最少,取工资前要统计出所有职工的工资所需各种币值(100,50,20,10,5,2,1 元共七种) 的张数。请编程完成。 2 典型贪心算法算法设计 1) 从键盘输入每人的工资。 2) 对每一个人的工资,用“贪婪”的思想,先尽量多地取大面额的币种,由大面额到小面额币种逐渐统计。 3) 利用数组应用技巧,将七种币值存储在数组 B。这样,七种币值就可表示为 B[i],i=1,2,3,4,5,6,7 。为了能实现贪婪策略, 七种币应该从大面额的币种到小面额的币种依次存储。 4) 利用数组技巧,设置一个有 7个元素的累加器数组 S。算法 main( ) { int i,j,n,GZ,A ; int B[8]={0,100,50,20,10,5,2,1},S[8]; input(n); for(i=1;i<=n;i++) { input(GZ); for(j=1,j<=7;j++) { A=GZ/B[j]; S[j]=S[j]+A; GZ=GZ-A *B[j];} } for(i=1;i<=7;i++) print(B[i], “---- ”, S[i]); } 算法说明每求出一种面额所需的张数后, 一定要把这部分金额减去: “GZ=GZ-A *B[j]; ”,否则将会重复计算。算法分析算法的时间复杂性是 O(n)。 2、取数游戏有2 个人轮流取 2n 个数中的 n 个数,取数之和大者为胜。请编写算法,让先取数者胜,模拟取数过程。问题分析这个游戏一般假设取数者只能看到 2n 个数中两边的数, 用贪婪算法的情况: 若一组数据为: 6,16,27,6,12,9,2,11,6,5 。用贪婪策略每次两人都取两边的数中较大的一个数, : 取数结果为: A 6,27,12,5,11=61 胜 B 16,6,9,6,2=39 但若选另一组数据: 16,27,7,12,9,2,11,6 。仍都用贪婪算法,先取者 A败。取数结果为: A 16,7,9,11=43 B 27,12,6,2=47 胜其实,若我们只能看到两边的数据,则此题无论先取还是后取都无必胜的策略。这时一般的策略是用近似贪婪算法。但若取数者能看到全部 2n 个数,则此问题可有一些简单的方法,有的虽不能保证所取数的和是最大,但确是一个先取者必胜的策略。