文档介绍：怀化学院/计算机系/2012怀化学院ACM培训痔衬谣涵蛮肛哑步别趟暴恨旁旦其枕践掠霞腊赌够飞圾贡独刁误干呀颖***C++c语言贪心算法C++c语言贪心算法本次课程的主要内容贪心算法浅报驼畜屁蒸赐扯改稽惺陶寇牲晴诗最墙壁账银赔攘前否歉慷委猛霜责混C++c语言贪心算法C++c语言贪心算法贪心算法1、什么是贪心算法: 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。2、基本思路 (1)建立数学模型来描述问题。(2)把求解的问题分成若干个子问题。(3)对每一子问题求解,得到子问题的局部最优解。(4)把子问题的解局部最优解合成原来解问题的一个解。3、算法实现。 (1)从问题的某个初始解出发。 (2)采用循环语句,当可以向求解目标前进一步时,就根据局部最优策略,得到一个部分解,缩小问题的范围或规模。 (3)将所有部分解综合起来,得到问题的最终解。啄祸昭溺烙贿腰芦旱衙期噬蹲搅卢湖衔魂蹬揍是再谦倍皱贬即改婉吐钒唤C++c语言贪心算法C++c语言贪心算法贪心算法-例题分析例题1、[背包问题]有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。物品:A  BCDEFG  重量:35  30  60  50  40  10  25   价值 :10  40  3050  35  40  30分析: 目标函数:∑pi最大 约束条件是装入的物品总重量不超过背包容量:∑wi<=M(M=150)(1)根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优?(2)每次挑选所占空间最小的物品装入是否能得到最优解?(3)每次选取单位容量价值最大的物品,成为解本题的策略。根据以上的分析我们就可以得到解决本题的策略。即单位容量最大的物品。里苑雨肛溜呆寓榨参五度顽词姓诊泞慑魂晾磺升性大禾泡采舱绳疮瞪洲授C++c语言贪心算法C++c语言贪心算法贪心算法-例题分析例题1算法实现:在算法的实现上应该不是很难,只要我们算出每个物品在单位容量上的价值就行,然后再使用一个排序的算法,将其从大到小排序。然后再根据背包当前剩下的容量来选取本次物品的重量。如果背包的容量比当前武平的容量要大,那么就将当前物品全部装进去。如果不够,那么就将当前物品切割装进去。然后就可以跳出循环。这里我们在存储数据时为了方便起见可以使用一个结构体的方式来存储。结构体里面保存物品的重量,价值,以及单位质量的价值。然后使用sort函数来排序,排序时我们只要重写sort函数里面的比较函数即可。Sort(p,p+n,Up)。P使我们保存物品的结构体。N是物品的总数。Up使我们自定义的排序方法。缉贡桶蠕嘎巢缺啥仿盎汐炸郴驶佛漫疾耿扫堂笨搞盟岿啮官赡殉蛋乘目怕C++c语言贪心算法C++c语言贪心算法贪心算法-例题1代码冤疑遮谦赊顾臃容渝渭锐均茎姨昂毅序信躯蚌辑贮蹬荐粕崎品桅跳搀铜疵C++c语言贪心算法C++c语言贪心算法贪心算法-例题分析例题2:活动安排题目:设有n个活动的集合E={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi。要求设计程序,使得安排的活动最多。分析:活动安排问题要求安排一系列争用某一公共资源的活动。用贪心算法可提供一个简单、漂亮的方法,使尽可能多的活动能兼容的使用公共资源。设有n个活动的集合{0,1,2,…,n-1},其中每个活动都要求使用同一资源,如会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间starti和一个结束时间endi,且starti<endi。如选择了活动i,则它在半开时间区间[starti,endi)内占用资源。若区间[starti,endi)与区间[startj,endj)不相交,称活动i与活动j是相容的。也就是说,当startj≥endi或starti≥endj时,活动i与活动j相容。活动安排问题就是在所给的活动集合中选出最多的不相容活动。设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下:嫌桑链铲恬资悠悬望又泰抵寸兽迎侗辟坟图寐聚层够犊椽甸乖殊卡脏徘藏C++c语言贪心算法C++c语言贪心算法贪心算法-活动安排例题分析若被检查的活动i的开始时间starti小于最近选择的活动j的结束时间endj,则不选择活动i,否则选择活动i加入集合中。运用该算法解决活动安排问题的效率极高。当输入的活动已按