C++c语言贪心算法.ppt

1、怀化学院/计算机系/2012,怀化学院ACM培训,本次课程的主要内容,贪心算法,贪心算法,1、什么是贪心算法: 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 2、基本思路 (1)建立数学模型来描述问题。 (2)把求解的问题分成若干个子问题。 (3)对每一子问题求解，得到子问题的局部最优解。 (4)把子问题的解局部最优解合成原来解问题的一个解。 3、算法实现。 (1)从问题的某个

2、初始解出发。 (2)采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模。 (3)将所有部分解综合起来，得到问题的最终解。,贪心算法-例题分析,例题1、背包问题 有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 物品 ：A B C D E F G重量 ：35 30 60 50 40 10 25价值：10 40 30 50 35 40 30,分析：目标函数： pi最大约束条件是装入的物品总重量不超过背包容量：wi=M( M=150) （1）根据贪心的策略，每次挑选价值最大

3、的物品装入背包，得到的结果是否最优？,（2）每次挑选所占空间最小的物品装入是否能得到最优解？,（3）每次选取单位容量价值最大的物品，成为解本题的策略。 根据以上的分析我们就可以得到解决本题的策略。即单位容量最大的物品。,贪心算法-例题分析,例题1算法实现： 在算法的实现上应该不是很难，只要我们算出每个物品在单位容量上的价值就行，然后再使用一个排序的算法，将其从大到小排序。然后再根据背包当前剩下的容量来选取本次物品的重量。如果背包的容量比当前武平的容量要大，那么就将当前物品全部装进去。如果不够，那么就将当前物品切割装进去。然后就可以跳出循环。这里我们在存储数据时为了方便起见可以使用一个结构体的方

4、式来存储。结构体里面保存物品的重量，价值，以及单位质量的价值。然后使用sort函数来排序，排序时我们只要重写sort函数里面的比较函数即可。Sort(p,p+n,Up)。P使我们保存物品的结构体。N是物品的总数。Up使我们自定义的排序方法。,贪心算法-例题1代码,贪心算法-例题分析,例题2：活动安排 题目： 设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si fi 。要求设计程序，使得安排的活动最多。,分析： 活动安排问题要求安排一系列争用某一公共资源

5、的活动。用贪心算法可提供一个简单、漂亮的方法，使尽可能多的活动能兼容的使用公共资源。设有n个活动的集合0，1，2，n-1，其中每个活动都要求使用同一资源，如会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间starti和一个结束时间endi，且startiendi。如选择了活动i，则它在半开时间区间starti,endi）内占用资源。若区间starti,endi)与区间startj,endj)不相交，称活动i与活动j是相容的。也就是说，当startjendi或startiendj时，活动i与活动j相容。活动安排问题就是在所给的活动集合中选出最多的不相容

6、活动。 设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：,贪心算法-活动安排例题分析,若被检查的活动i的开始时间starti小于最近选择的活动j的结束时间endj，则不选择活动i，否则选择活动i加入集合中。运用该算法解决活动安排问题的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。,实现代码：,贪心算法-例题分析例题3：克鲁斯卡尔算法-最小生成树,假定输入如下： 6 0 6 1 5 0 0 6 0 5 0 3 0 1 5 0 5 6 4 5

7、 0 5 0 0 2 0 3 6 0 0 6 0 0 4 2 6 0,由于是对称三角形，可以只使用下三角或上三角，在此使用下三角部分，即ij的部分。,演示算法实现过程。,人工模拟,1,2,3,4,5,5,5,6,6,6,最小生成树的耗费为15,算法难点,从刚才的演示过程，可知算法实现有两个难点： （1）边的选择要求从小到大选择，则开始显然要对边进行升序排序。 （2）选择的边是否需要，则从判断该边加入后是否构成环入手。,难点解决（一）,（1）对边升序排序 方法可根据以前数据结构中选择合适的排序。 在此采用链式结构，通过插入排序完成。 每一结点存放一条边的左右端点序号、权值及后继结点指针。,难点解决（二）,（2）边的加入是否构成环 一开始假定各顶点分别为一组，其组号为端点序号