主讲人：刘雅琼计算机大学05级QQ：591294402Email：liuyaqiong1988@hotmail.com最优装载问题单源最短路径问题区间问题哈夫曼编码贪心算法简介贪心算法是一个解决最优子结构问题的算法。顾名思义，贪心算法总是作出在当前看来最好的选择，也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。贪心算法简介其实贪心算法不能对所有问题都得到整体最优解，但对许多问题它能形成整体最优解。诸如，图的单源最短路径问题，最小生成树问题等。在一些情况下，虽然贪心算法不能得到整体最优解，其最终结果却是最优解的挺好近似。问题：有一批集装箱要装上一艘载重量为的客轮，其中集装箱的重量为,在装载容积不受限制的情况下，应怎样装载能够把尽可能多的集装箱装上货轮？本题可方式化描述为max其中，变量本例也许可用贪心算法求解。将集装箱按重量由小到大排序，重量最轻者先装，每一次都选购剩余集装箱中最轻的放入，直至不能放入为止。得到本问题的一个最优解。#includeiostream#includealgorithmusingnamespacestd;constint10002;structnodeintid;intweight;intcmp(nodereturna.weightb.weight;}//定义的比较函数cmp，//用于排序intmain()inti,c,n,nc;while(scanf("%d%d",问题描述已知图G=(V,E)，我们希望找出从某个给定源顶点sV到每位顶点vV的最短路径。
Dijkstra算法每次在剩余的点中选购距离源点s近来的点。直至找到目的顶点d。10Dijkstra(G,w,s)由于Dijkstra算法总是在V-S中选择“最轻”或“最近”的定点插入集合S中，所以我们说它使用策略。11Dijkstra是应用贪心算法设计策略的一个典型事例。源点到定点u的最漏电为dist[u]。它这些贪心选择为何能引起最优解呢？简单证明（反证法）假定存在一条从源点s到u且厚度比dist[u]更短的路，设这条路经过在S之外的定点x最后抵达u,则dist[x]0,故而得到dist[x]dist[u],而这样的话x将会先于u被选入S集合内。这与假定条件矛盾。12注：单源最短路径的dijkstra算法、最小生成树的Prim算法和Kruskal算法都可以看做是应用贪心算法设计策略的典型事例。11月2日的讲堂早已讲过这种了，这儿不再赘言。这儿只举一个简单反例：TOJ2976题目描述：要找寻从商店到赛场的最短的路线。输入：每组数据两个整数N、M（N=100，M=10000），N表示大道上有几个路口，1是商店哈夫曼编码贪心算法时间复杂度，N是赛场，M表示有几条路。N=M=0表示输入结束。接出来M行，每行3个整数A，B，C（1=A,B=N,1=C=1000）,表示在路口A与B之间有一条路，工作人员需C分钟走过这条路。
输出：对每组输入，输出一行，表示工作人员从商店走到赛场的最短时间13直接运用Dijkstra算法即可。15在联赛中，有好多问题最终都能转化为区间问题：诸如从若干个区间中选出一些满足一定条件的区间、将各个区间分配到一些资源中、或者将一些区间以某种次序放置等。如活动安排问题、机器调度问题等这类问题变化繁杂，解法各异。下边介绍几种常见模型。16数轴上有n个区间，选出最多的区间，致使这种区间不相互重叠。依次选择所有能选的区间17例题：TOJ2867某人想要出席一系列活动，已知每位活动的开始时间和持续时间，问他最多能出席几个活动。SampleInputSampleOutput剖析：本题已知每位活动的起始时间和持续时间，由此可得到活动的起始时间和中止时间，即各区间的两个端点。其实，这是最大区间调度问题。应用前面所讲的贪心算法即可求解。19有n个区间和无限多的资源，每位资源上的区间之间不相互重叠。将每位区间都分配到某个资源中，使用到的资源数目最小。20定义区间集合深度d为包含任意一点的区间数目的最大值依次将区间任意地分配到d个资源中21d的估算方式：将每位区间拆成两个风波点，按座标从小到大排序，次序处理每位区间。
记录一个值，表示当前点被包含次数。每次遇见区间的上端点就+1，遇见右端点就-1。的值就是在该过程中的最大值。注意两个相同座标不同类型的风波点的位置关系和区间是否能在端点处重叠有关，这在排序过程中应当注意。22例：TOJ2894Meetings（07年保研复试题）题目描述：给出大会的起止时间（即给出了各个区间），问安排这种大会最少须要多少个大会室?（一个大会结束的时刻，另一个大会可以马上开始）剖析：大会室—多个资源；大会—区间；将每位区间都分配给某个资源，使用到的资源数目最小，即要求解的是区间深度d。23注意：上面提及，加1与减1的先后次序与每位区间在端点处能否重叠有关。对本题而言，似乎要求可以重叠，故应当先减1再]分别储存各区间的上端点和右端点。j1和j2分别是链表a[]的下标。r是贯串整个for循环的变量，遇见区间右端点则加1，遇见区间上端点则减1。result为for循环过程中r的最大值，即区间深度d。TOJ289424TOJ2894//对上端点进行排序sort//对右端点进行排序j125TOJ2894MAX;)//MIN和MAX分别是所有区间最上端点和最右端result为最后结果elsebreak;//最后输出结果26有n个宽度固定、但位置可变的区间，将它们全部放置在[0,+)上。
每位区间有两个已知参数：宽度t为其右端点座标。定义放置所有区间，使它们不相互重叠且最大延后L最小。max27次序安排各区间最终时限dSoutheastern2007Problem一个建行家收到了N个按揭申请，每位按揭最晚都要在前完成，收益为，每位按揭均须要一个单位时间来处理，工行在同一时间内最多可接受L个按揭，问怎么安排能使获得收益最大？将每位按揭申请看作一个单位宽度、位置可变且带权的区间，则题目转化为选出一些区间，将它们不相互重叠地置于L个资源上，使收益最大，且区间的上端点不得超过。可用贪心算法解决该问题。将这种区间根据残差从大到小排序，次序处理每位区间。设因为区间都是单位宽度的，我们可以用一维链表来记录当前的情况,表示被覆盖次数，按照题意有处理第i个区间时，若可以选择该区间，），则将该区间放置到一个i最大的一个位置，即，否则就不选择该区间。与上例相像的一道题：TOJ1681惟一的一点不同是toj1681同一时刻只能处理一件产品，即上页算法中的L是1。因而toj1681要简单一些。你们回家可以根据上述算法做一做。参见如下部份代码：sortcmp);memset-1,sizeof(s));参见如下部份代码：sortcmp);memset-1,sizeof(s));有n个区间，选择尽量少的区间，致使这种区间完全覆盖某线段[s,t]。每次选择覆盖点s的区间中右端点座标最大的一个，并更新s直至所选区间已包含t32有n个区间，m个点。若某区间包含了某点哈夫曼编码贪心算法时间复杂度，则构成一对匹配关系。选出最多的区间和相同数目的点，使对应的区间和点构成匹配关系。33算法：
