算法设计 郑宇军 石海鹤 陈胜勇 算法设计（第6章）

《算法设计 郑宇军 石海鹤 陈胜勇 算法设计（第6章）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章贪心法简介最小生成树单源最短路径贪心调度贪心法简介找零钱问题10元−3元=7元:5+2100元−3元=97元:50+20+20+5+2100元−14元=86元:50+20+10+5+1没有更优的找钱方案每次尽可能地选取最大面额的钞票贪心法简介找零钱问题每次尽可能地选取最大面额的钞票[贪心算法]AlgorithmChange(intx)beginleta1=a2=a3=0;if(x≥5)thena31;xx−5;while(x≥2)doa2a2+1;xx−2;a1x;return(a1,a2,a3);end贪心法简介找零钱问题最优性证明：（1）若x的值为1,2

2、,5，那么所需的零钱为1张，这显然是最少的。（2）否则，所需的钱数至少为2张。算法对3,4,6,7生成的找钱方案分别为2+1,2+2,5+1,5+2，这显然也是最少的。（3）若x的值为8和9，算法生成的找钱方案分别为5+2+1和5+2+2；而用2张钞票不能找出8元或9元的零钱，因此算法的结果也是最少的。如果将x的值扩大到100以内，并增加面值为50,20和10元的钞票，那么使用贪心算法仍然能够得到最优的找钱方案，即每次尽可能地选取最大面额的零钞。每次尽可能地选取最大面额的钞票贪心法简介贪心算法：在问题求解的过程中采用“贪婪”的策略来构造目标解。实现起来较为简单难点通常在于算

3、法的正确性证明贪心法简介最大装载问题输入：总重量限制W，以及n个物品的重量A={a0,a1,…,an−1}输出：A的一个子集A*，其和不大于W，且元素数量尽可能大W=1000,A={400,350,300,250,240,180,150,120}选取120+150+180+240+250最优（不可能选出5个以上的物品）每次尽可能地选取重量最小的物品贪心法简介每次尽可能地选取重量最小的物品[贪心算法]AlgorithmMaxLoad(W:int;A:int[])beginSort(A);leti=0;while(W>0)doif(A[i]≤W)thenWW-A[i];ii

4、+1;returnA[0..i];end最大装载问题贪心法简介最优性证明：【引理6.1】设A*是问题P(A,W)的一个最优解，那么a0总是可以包含在A*中。【引理6.2】设A*是问题P(A,W)的一个最优解，且a0A*，那么A*{a0}也是问题P(A{a0},W−a0)的一个最优解。【定理6.1】贪心算法6.2输出最大数量装载问题P(A,W)的一个最优解。每次尽可能地选取重量最小的物品最大装载问题最小生成树树:无回路的连通子图生成树：含图中所有顶点的树最小生成树:加权图中权值最小的生成树最小生成树最小生成树:加权图中权值最小的生成树abcde1810282420161

5、512abcde10242015abcde1810281210abcde182012穷举法:O(2n)最小生成树Prim算法:每次选取连接V'和V−V'的权值最小的边abcde1810282420161512abcde18101512最小生成树O(n2)AlgorithmPrim(V:set;E:set;w:int[,])beginletn=

6、V

7、,Y=E{E[0]};letV’={E[0].a,E[0].b},E’={E[0]},tw=w[E[0]];while(

8、V’

9、

10、Y

11、)doif(Y[i].a

12、V’Y[i].bV’)(Y[i].aV’Y[i].bV’)break;ii+1;lete=Y[i];//e为V’和V−V’之间的最小边E’E’{e};V’V’{e.a,e.b};twtw+w[e];YY{e};return(E’,tw);endPrim算法:每次选取连接V'和V−V'的权值最小的边最小生成树最优性证明：（1）权值最小的边e0可以包含在G的最小生成树中。（2）设T'=为最小生成树T的一棵子树，e为连接V'和V−V′之间的所有边中权值最小的一条，那么e可以包含在最小生成树中。按数学归纳法，Prim算法的结果是一棵最小生

13、成树。Prim算法:每次选取连接V'和V−V'的权值最小的边最小生成树Kruskal算法:每次选取不产生回路的最小边abcde1810282420161512abcde18101512最小生成树Kruskal算法:每次选取不产生回路的最小边O(mlogm)AlgorithmKruskal(V:set;E:set;w:int[,])beginletn=

14、V

15、,Y=E{E[0]};letV’={{E[0].a,E[0].b}},E’={E[0]},tw=w[E[0]];while(

16、V’[