[计算机软件及应用]矿大算法第4章 贪心算法-2.ppt

《[计算机软件及应用]矿大算法第4章 贪心算法-2.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.2活动安排问题问题的提出n个活动的集合E={1,2,…,n},在某一时间内要独占使用某个资源。每个活动i使用资源的起始时间为Si，终止时间为Fi。活动i和活动j相容：是指[Si,Fi)与[Sj,Fj)不相交，即：Sj>=Fi或Si>=Fj要求尽可能多地安排活动。即从活动集合E中选出最大相容活动子集。思路：最早结束的活动，优先安排。对f1,f2,…,fn从小到大排序,时间O(nlogn)算法：templatevoidgreedyselector(intn,Ts[],Tf[],boolA[]

2、){A[1]=true;intj=1;//j记录最近入选的活动for(inti=2;i<=n;i++){if(s[i]>=f[j]){//活动i和活动j相容A[i]=true;j=i;}elseA[i]=false;}}//时间复杂性：O(n)（不包括排序）[算法思路]将n个活动按结束时间非减序排列,依次考虑活动i,若i与已选择的活动相容,则添加此活动到相容活动子集.设待安排的11个活动起止时间按结束时间的非减序排列最大相容活动子集(1,4,8,11),也可表示为等长n元数组:(1,0,0,1,0,0,0,

3、1,0,0,1)思考如下具有11个活动安排的问题？1234567891011503531868122965784111012141312345678910111305356882124567891011121314is[i]f[i]Fj总是当前活动集合中结束最晚的活动一旦Si>=Fj，则活动i和活动j相容，将活动i加入A中，i取代j成为最近加入的活动直观上，该算法每次总是选取最早完成时间的活动，这样就为安排其它活动留下尽可能多的时间，从而能安排更多的活动。证明上述贪心算法一定能得到最优解：设n个活动已经按照

4、结束时间的非减次序排列，集合E={1,2,…,n}。首先，活动1包含在最优解中。设A是一个最优解，且A中活动也按Fi递增排序，A中第一个活动为k。假如k≠1，那么构造B=A-{k}∪{1}，由F1<=Fk，A中活动互为相容A中活动互为相容；A和B中的活动数目相同，A是最优解B是最优解。所以，存在一个以贪心选择开始的最优解。其次，活动1入选之后，问题变为对E中所有与活动1相容活动的安排子问题。若A是E的最优解，则A’=A-{1}是E’={i∈E

5、Si≥f1}的最优解，否则，若B’优于A’，则B’∪{1}优

6、于A，产生矛盾。由数学归纳法贪心法最终能产生最优解。注意：上述算法是考虑尽可能多地安排活动数目。如果从资源的拥有者角度考虑，要尽可能减少资源闲置时间，应采取什么安排策略？贪心算法是否有效？4.3最优装载问题描述：将重量为w1,…,wn的集装箱装上载重量为C轮船，要求尽可能多地装入。应如何装载？形式化描述：目标函数极大化maxΣxi约束条件Σwixi≤cxi∈{0,1}1≤i≤n实际上，是0/1背包问题的特殊简化：P1=P2=…=Pn=1船可以分步装载，每步装一个货箱，且需要考虑装载哪一个货箱。根据这种思想

7、可利用如下贪心准则：从剩下的货箱中，选择重量最小的货箱。这种选择次序可以保证所选的货箱总重量最小，从而可以装载更多的货箱。根据这种贪心策略，首先选择最轻的货箱，然后选次轻的货箱，如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。贪心策略：重量轻的集装箱，优先装载。算法说明：时间复杂性：排序O(nlogn)数组x：存放最优解。起初，xi=0数组w：存放各个集装箱重量。Sort(w,t,n)：t[i]存放w中第i小元素的位置例：W={15,9,7,20,8}i=12345t[i]=35214for(

8、i=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w[t[i]];}[例]设n=8，[w1，…w8]=[100,200,50,90,150,50,20,80]，c=400。[算法思路]将装船过程划为多步选择，每步装一个货箱，每次从剩下的货箱中选择重量最轻的货箱.如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。所考察货箱的次序为:7,3,6,8,4,1,5,2。货箱7,3,6,8,4,1的总重量为390个单位且已被装载,剩下的装载能力为10,小于任意货箱.所以得到解[

9、x1,...x8]=[1,0,1,1,0,1,1,1]最优装载的贪心算法templatevoidLoading(intx[],Typew[],Typec,intn){int*t=newint[n+1];Sort(w,t,n);//按货箱重量排序/for(inti=1;i<=n;i++)x[i]=0;for(inti=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w