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