ACM程序设计基础之贪心法.ppt

贪心算法,贪心法的设计思想,贪心法的求解过程,贪心法的基本要素,贪心法的应用举例,贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。 这种局部最优选择并不总能获得整体最优解（Optimal Solution），但通常能获得近似最优解（Near-Optimal Solution）。,1 贪心法的设计思想,引例 找零钱,一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。 假设提供了数目不限的面值为2 5美分、1 0美分、5美分、及1美分的硬币。 售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪婪准则如下：每一次选择应使零钱数尽量增大。为保证解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。,算法思想,为使找回的零钱的硬币数最小，不考虑找零钱的所有各种方案，而是从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，只当不足大面值币种的金额才会去考虑下一种较小面值的币种。这就是在采用贪婪法。 这种方法在这里之所以总是最优，是因为银行对其发行的硬币种类和硬币面值的巧妙安排。 如果只有面值分别为1，5和11单位的硬币，而希望找回总额为15单位的硬币，按贪婪算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币。但最优的解答应是3个5单位面值的硬币。,贪心法求解的问题的特征： （1）最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。 （2）贪心选择性质 所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。,动态规划法通常以自底向上的方式求解各个子问题，而贪心法则通常以自顶向下的方式做出一系列的贪心选择。,2 贪心法的求解过程,用贪心法求解问题应该考虑如下几个方面： （1）候选集合C：为了构造问题的解决方案，有一个候选集合C作为问题的可能解，即问题的最终解均取自于候选集合C。例如，在付款问题中，各种面值的货币构成候选集合。 （2）解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成一个满足问题的完整解。例如，在付款问题中，已付出的货币构成解集合。,（3）解决函数solution：检查解集合S是否构成问题的完整解。例如，在付款问题中，解决函数是已付出的货币金额恰好等于应付款。 （4）选择函数select：即贪心策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。例如，在付款问题中，贪心策略就是在候选集合中选择面值最大的货币。 （5）可行函数feasible：检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。例如，在付款问题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款。,贪心法的一般过程 Greedy(C) /C是问题的输入集合即候选集合 S= ; /初始解集合为空集 while (not solution(S) /集合S没有构成问题的一个解 x=select(C); /在候选集合C中做贪心选择 if feasible(S, x) /判断集合S中加入x后的解是否可行 S=S+x; C=C-x; return S; ,例1、 活动安排问题,活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。,例1、活动安排问题,设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间begini和一个结束时间endi,且begini endi 。如果选择了活动i，则它在半开时间区间begini, endi)内占用资源。若区间begini, endi)与区间beginj, endj)不相交，则称活动i与活动j是相容的。也就是说，当beginiendj或beginjendi时，活动i与活动j相容。,a 和 b 事件的开始时刻小于结束时刻 Begina= Enda 记为 b a 这时 b 事件与 a 事件不重叠.,例1、活动安排问题,例：设待安排的12个活动的开始时间和结束时间按结束时间的非减序排列如下：,找出 时间上不重叠的事件： 2#,9# 2#,8#,10# 2#,8#,11# 0#,3#,8#,10# 0#,3#,8#,11# 0#,1#,5#,8#,10# 0#,1#,5#,8#,11# 0#,1#,6#,10# 0#,1#,6#,11#,每个都选择最早结束的序列-贪心策略 0#-1#-5#-8#-10# 这是最长序列,#include const int N=12; void OtputResult(int SelectN); cout“ 0”; for( int i=1; iN; i+ ) if ( Select i =1) cout“,” i ; cout “ “ endl; ,void main( ) int BeginN=1,3,0,3,2,5,6,4,10,8,15,15; int EndN=3,4,7,8,9,10,12,14,15,18,19,20; int SelectN=0,0,0,0,0,0,0,0,0,0,0,0; int i=0;/当前最早结束的事件 /当前可选事件的最早开始时间 int TimeStart=0;,while( i =TimeStart ) Select i =1; TimeStart=End i ; i +; OutputResult ( Select ) ; ,3、贪心算法的基本要素,对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。 但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。,3 贪心算法的基本要素,1.贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。,3 贪心算法的基本要素,2.最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。,例2、 背包问题,给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大?,于是，背包问题归结为寻找一个满足约束条件式7.1，并使目标函数式7.2达到最大的解向量X=(x1, x2, , xn)。,设xi表示物品i装入背包的情况，根据问题的要求，有如下约束条件和目标函数：,（式7.1）,（式7.2）,至少有三种看似合理的贪心策略： （1）选择价值最大的物品，因为这可以尽可能快地增加背包的总价值。但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗得太快，使得装入背包的物品个数减少，从而不能保证目标函数达到最大。 （2）选择重量最轻的物品，因为这可以装入尽可能多的物品，从而增加背包的总价值。但是，虽然每一步选择使背包的容量消耗得慢了，但背包的价值却没能保证迅速增长，从而不能保证目标函数达到最大。 （3）选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者之间寻找平衡。,应用第三种贪心策略，每次从物品集合中选择单位重量价值最大的物品，如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量，然后我们就面临了一个最优子问题它同样是背包问题，只不过背包容量减少了，物品集合减少了。因此背包问题具有最优子结构性质。,120 50 背包 180 190 200 (a) 三个物品及背包 (b) 贪心策略1 (c) 贪心策略2 (d) 贪心策略3,例如，有3个物品，其重量分别是20, 30, 10，价值分别为60, 120, 50，背包的容量为50，应用三种贪心策略装入背包的物品和获得的价值如图所示。,设背包容量为C，共有n个物品，物品重量存放在数组wn中，价值存放在数组vn中，问题的解存放在数组xn中。,算法的时间主要消耗在将各种物品依其单位重量的价值从大到小排序。因此，其时间复杂性为O(nlog2n)。,Another one 最优合并问题,给定k 个排好序的序列s1 , s2, sk , 用2 路合并算法将这k 个序列合并成一个 序列。假设所采用的2 路合并算法合并2 个长度分别为m和n的序列的m + n .试设 计一个算法确定合并这个序列的最优合并 顺序，使所得总值最少和最大。,解题思路,先确定贪心策略： 总的想法是希望总的合并长度最小。由 最优子结构性质可知，子问题的长度也是 最短的，也就是最后的合并的两个数是最 小的，亦即每次合并的都是最小的两个 数，这样就得出来玩解决问题的办法。,最后实现,思路很清晰了：每次都取加入了新数之后的集合中的最小值和次小值合并成一个新的数，并删除这两个数，把新数加入集合，循环到只有两个数了位置。 取最小值：不断循环，不断