《cc语言贪心算法》.ppt

怀化学院/计算机系/2012
怀化学院ACM培训
整理课件
本次课程的主要内容
贪心算法
整理课件
贪心算法
1、什么是贪心算法:
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选怀化学院/计算机系/2012
怀化学院ACM培训
整理课件
本次课程的主要内容
贪心算法
整理课件
贪心算法
1、什么是贪心算法:
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
2、基本思路
(1)建立数学模型来描述问题。
　 (2)把求解的问题分成若干个子问题。
　 (3)对每一子问题求解，得到子问题的局部最优解。
　 (4)把子问题的解局部最优解合成原来解问题的一个解。
3、算法实现。
(1)从问题的某个初始解出发。
(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）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占空间最小的物品装入是否能得到最优解？
（3）每次选取单位容量价值最大的物品，成为解本题的策略。
根据以上的分析我们就可以得到解决本题的策略。即单位容量最大的物品。
整理课件
贪心算法-例题分析
例题1算法实现：
在算法的实现上应该不是很难，只要我们算出每个物品在单位容量上的价值就行，然后再使用一个排序的算法，将其从大到小排序。然后再根据背包当前剩下的容量来选取本次物品的重量。如果背包的容量比当前武平的容量要大，那么就将当前物品全部装进去。如果不够，那么就将当前物品切割装进去。然后就可以跳出循环。这里我们在存储数据时为了方便起见可以使用一个结构体的方式来存储。结构体里面保存物品的重量，价值，以及单位质量的价值。然后使用sort函数来排序，排序时我们只要重写sort函数里面的比较函数即可。Sort(p,p+n,Up)。P使我们保存物品的结构体。N是物品的总数。Up使我们自定义的排序方法。
整理课件
贪心算法-例题1代码
整理课件
贪心算法-例题分析
例题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个活动的开始时间和结束时间按结束时间的非减序排列如下：
整理课件
贪心算法-活动安排例题分析
若被检查的活动i的开始时间starti小于最近选择的活动j的结束时间endj，则不选择活动i，否则选择活动i加入集合中。运用该算法解决活动安排问题的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活