算法分析与设计[贪心法].ppt

第三章贪心方法3.1什么是贪心方法3.1什么是贪心方法贪心方法的抽象化控制3.2背包问题背包问题实例贪心方法的数据选择策略(1)贪心方法的数据选择策略(2)贪心方法的数据选择策略(2)贪心方法的数据选择策略(3)背包问题的贪心算法最优解的证明最优解的证明最优解的证明若k>j，若yk>xk=0，则∑wiyi>M,这与Y是可行解矛盾。因此，结论yk<xk成立。
现在，假定把yk增加到xk，那么必须从(yk+1,…,yn)中减去同样多的量，使得所用的总容量仍为M。这导致一个新的解Z=(z1,…,zn)，其中，zi=xi,1≤i≤k，并且∑wi(yi-zi)=wk(zk-yk)。
因此，对于Z有
∑pizi=∑piyi+(zk-yk)pk-∑(yi-zi)pi

=∑piyi+(zk-yk)wkpk/wk-∑(yi-zi)wipi/wi

≥∑piyi+[(zk-yk)wk-∑(yi-zi)wi]pk/wk

=∑piyi 最优解的证明课后思考题3.3带有限期的作业排序带有限期的作业排序实例带限期的作业排序算法例3.2带限期的作业排序算法定理3.2定理3.2证明定理3.2证明（续）定理3.2证明（续）如何判断J的可行性可行解的确定定理3.2证明带限期序作业排序的处理带限期序作业排序的贪心算法一种更快的作业排序算法一种更快的作业排序算法(续)作业排序的一个更快算法课后思考题3.4最优归并模式什么是归并模式X1，X2和X3是各自有30个记录、20个记录和10个记录的三个已分类文件。
归并X1和X2需要50次记录移动，再与X3归并则还要60次移动，其所需要的记录移动次数总量为110。
如果首先归并X2和X3，需要30次移动，然后再归并X1，需要60次移动，则所要移动记录的总量为90。
因此，第二个归并模式比第一个要好。最优归并模式的实现二路归并模式最优归并模式的实现二元归并树算法二元归并树算法二元归并树算法的实例二元归并树算法的计算时间最优解证明最优解的证明最优解的证明3.5最小生成树Prim算法Prim算法Kruskal算法Kruskal算法3.6单源点最短路径贪心策略求解贪心策略求解贪心策略求解产生最短路径的贪心方法生成最短路径的贪心算法算法实例算法实例1、多机调度问题：设有n项独立的作业{1,2,…,n},由m台相同的机器加工处理。作业i所需要的处理时间为ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分成更小的子作业。多机调度问题要求给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完。利用贪心策略，设计算法解决多机调度问题，并计算其时间复杂度。
2、设有7项独立的作业{1,2,3,4,5,6,7},要由三台机器M1,M2,M3处理。各个作业所需要的处理时间分别为{2,14,4,16,6,5,3}。利用你设计的贪心算法，安排作业的处理顺序使得机器处理作业的时间最短。