第3篇 核心篇-贪婪算法

算法设计与分析

Design

and

AnalysisofComputerAlgorithms

第3篇核心篇贪婪算法贪婪算法（贪心法）的设计思想贪婪算法的求解过程贪婪算法的基本要素贪婪算法的应用举例教学内容：贪婪算法的设计思想【基本思想】将问题的求解过程看作是一系列选择，每次选择一个输入，每次选择都是当前状态下的最好选择（局部最优解），每作一次选择后，所求问题会简化为一个规模更小的子问题，从而通过每一步的最优解逐步达到整体的最优解。

贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总能获得整体最优解（OptimalSolution），但通常能获得近似最优解（Near-OptimalSolution）。引例[找零钱]一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为25美分、10美分、5美分、及1美分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪婪准则如下：

每一次选择应使零钱数尽量增大。为保证解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。算法思想为使找回的零钱的硬币数最小，不考虑找零钱的所有各种方案，而是从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，只当不足大面值币种的金额才会去考虑下一种较小面值的币种，这就是在采用贪婪法。这种方法在这里之所以总是最优，是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如果只有面值分别为1，5和11单位的硬币，而希望找回总额为15单位的硬币，按贪婪算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币。但最优的解答应是3个5单位面值的硬币。币种统计问题【例】某单位给每个职工发工资（精确到元）。为了保证不要临时兑换零钱，且取款的张数最少，去工资钱要统计所以职工的工资所需各种币种（100,50,20,10,5,2,1共7种）的张数，请编程完成。【算法设计】1、为了保证不要临时兑换零钱，且取款的张数最少，应该对每一个人的工资，用“贪婪”的思想，先尽量多地取大面额的币种，由大面额到小面额币种逐步统计。2、利用数组应用技巧，将7种币值存储在数组中，从大面额的币种到小面额的币种依次存储。币种统计问题币种统计问题inti,j,n,GZ,A,B[7]={100,50,20,10,5,2,1}; staticintS[7]; cin>>n;//输入人数 for(i=0;i<n;i++) { cin>>GZ;//输入每人的工资 for(j=0;j<7;j++) { A=GZ/B[j]; S[j]+=A; GZ=GZ-A*B[j]; } } for(i=0;i<7;i++) cout<<B[i]<<"-----"<<S[i]<<endl;//输出每种币种的张数2贪心法的求解过程

用贪心法求解问题应该考虑如下几个方面：（1）候选集合C：为了构造问题的解决方案，有一个候选集合C作为问题的可能解，即问题的最终解均取自于候选集合C。例如，在付款问题中，各种面值的货币构成候选集合。（2）解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成一个满足问题的完整解。例如，在付款问题中，已付出的货币构成解集合。

（3）解决函数solution：检查解集合S是否构成问题的完整解。例如，在付款问题中，解决函数是已付出的货币金额恰好等于应付款。

（4）选择函数select：即贪心策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。例如，在付款问题中，贪心策略就是在候选集合中选择面值最大的货币。（5）可行函数feasible：检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。例如，在付款问题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款。

贪心法的一般过程Greedy(C)//C是问题的输入集合即候选集合{S={};//初始解集合为空集while(notsolution(S))//集合S没有构成问题的一个解{x=select(C);//在候选集合C中做贪心选择iffeasible(S,x)//判断集合S中加入x后的解是否可行S=S+{x};C=C-{x};}returnS;}活动安排问题

活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。活动安排问题【例】设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间begin[i]和一个结束时间end[i],且begin[i]<end[i]。如果选择了活动i，则它在半开时间区间[begin[i],end[i])内占用资源。若区间[begin[i],end[i])与区间[begin[j],end[j])不相交，则称活动i与活动j是相容的。也就是说，当begin[i]≥end[j]或begin[j]≥end[i]时，活动i与活动j相容。【问题】找出时间上不重叠的事件【算法设计思想】a和b活动的开始时刻小于结束时刻Begin[a]<End[a]Begin[b]<End[b]b活动的开始时刻大于等于a活动的结束时刻,即Begin[b]>=End[a]记为b>a这时b活动与a活动不重叠,则选择活动b加入集合中，否则不选择该活动。活动安排问题【例】设待安排的12个活动的开始时间和结束时间按结束时间的非减序排列如下：i01234567891011begin[i]130325641081515end[i]3478910121415181920constintN=12;voidGreedySelector(intBegin[],intEnd[],intSelect[]){ inti,j; Select[0]=1; j=0; for(i=1;i<N;i++) {

if(Begin[i]>=End[j]) { Select[i]=1; j=i; } else Select[i]=0; }}//输出选择的活动voidOutputResult(intSelect[N]){ cout<<"{0";for(inti=1;i<N;i++)

if(Select[i]==1)

cout<<","<<i;cout<<"}"<<endl;}voidmain(){ intBegin[N]={1,3,0,3,2,5,6,4,10,8,15,15};//活动的最早开始时间intEnd[N]={3,4,7,8,9,10,12,14,15,18,19,20};//活动的最早结束的事件 staticintSelect[N]; intTimeStart=0; GreedySelector(Begin,End,Select); OutputResult(Select);}运行结果：3、贪心算法的基本要素 对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。3贪心算法的基本要素【贪心选择性质】

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。

【算法缺点】对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。3贪心算法的基本要素【最优子结构性质】

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。0-1背包问题：整数背包

给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。背包问题(KnapsackProblem)背包问题：分数背包

与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。相同：这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。区别：背包问题具有贪心选择性质，而0-1背包问题却不具有贪心选择性质，不能用贪心算法求解。背包问题(KnapsackProblem)24背包问题(KnapsackProblem)【问题描述】已知有n种物品和一个可容纳W重量的背包，每种物品I的重量为wi，假定将物品I的某一部分xi放入背包就会得到pixi的效益(0≤xi≤1,pi>0)，采用怎样的装包方法才会使装入背包物品的总效益为最大呢？【问题的形式描述】极大化： ∑pixi

约束条件：∑wixi≤W

0≤xi≤1,pi>0,wi>0,1≤i≤n1≤i≤n1≤i≤n解的意义:xi表示物品i装入背包的部分占该物品全部的比例（1）选择价值最大的物品，因为这可以尽可能快地增加背包的总价值。但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗得太快，使得装入背包的物品个数减少，从而不能保证目标函数达到最大。（2）选择重量最轻的物品，因为这可以装入尽可能多的物品，从而增加背包的总价值。但是，虽然每一步选择使背包的容量消耗得慢了，但背包的价值却没能保证迅速增长，从而不能保证目标函数达到最大。（3）选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者之间寻找平衡。至少有三种看似合理的贪心策略：背包问题(KnapsackProblem)背包问题(KnapsackProblem)方案1：按物品价值降序装包方案2：按物品重量升序装包方案3：按物品价值与重量比值的降序装包

应用第三种贪心策略，每次从物品集合中选择单位重量价值最大的物品，如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量，然后我们就面临了一个最优子问题——它同样是背包问题，只不过背包容量减少了，物品集合减少了。因此背包问题具有最优子结构性质。

背包问题(KnapsackProblem)

首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 用贪心算法解背包问题的基本步骤：3贪心算法的基本要素voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);//改变数组w和v的排列顺序，使其按单位重量价值v[i]/w[i]降序排列inti;for(i=1;i<=n;i++)x[i]=0;////初始化解向量floatc=M;//背包剩余容量for(i=1;i<=n;i++){if(w[i]>c)break;//当该物品重量大于剩余容量跳出x[i]=1;c-=w[i];//确定背包新的剩余容量}if(i<=n)x[i]=c/w[i];}//选择物品的一部分将背包填满3贪心算法的基本要素算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O（nlogn）。为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。

对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。3贪心算法的基本要素应用--货箱装船

货箱装船问题：设有编号为0…n-1的n种物品，重量分别为w0…wn-1，船载重为c，如何装载，使船可以装载更多的货箱。1、算法设计采用贪婪算法船可以分步装载，每步装一个货箱，且需要考虑装载哪一个货箱。根据这种思想可利用如下贪婪准则：从剩下的货箱中，选择重量最小的货箱。这种选择次序可以保证所选的货箱总重量最小，从而可以装载更多的货箱。根据这种贪婪策略，首先选择最轻的货箱，然后选次轻的货箱，如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。货箱装船#include<iostream.h>voidIndirectSort(intw[],intt[],intn){//Clugetotestwhenweightsalreadyinorder.for(inti=1;i<=n;i++)t[i]=i;}template<classT>voidContainerLoading(intx[],Tw[],Tc,intn){//Greedyalgorithmforcontainerloading.//Setx[i]=1iffcontaineri,1<=i<=nisloaded.//cisshipcapacity,wgivescontainerweights.//doindirectaddressingsortofweights

//tistheindirectaddressingtable

货箱装船

int*t=newint[n+1];IndirectSort(w,t,n);for(inti=1;i<=n;i++)x[i]=0;//selectobjectsinorderofweightfor(inti=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w[t[i]];}//remainingcapacitydelete[]t;}货箱装船voidmain(void){intw[13]={0,20,50,50,80,90,100,150,200},x[13];ContainerLoading(x,w,400,8);cout<<"Loadingvectoris"<<endl;for(inti=1;i<=8;i++)cout<<x[i]<<'';cout<<endl;}2、贪心选择性质 可以证明最优装载问题具有贪心选择性质。3、最优子结构性质 最优装载问题具有最优子结构性质。 由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法ContainerLoading的正确性。 算法ContainerLoading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为O(nlogn)。

多机调度问题【多机调度问题】设有

n个独立的作业{1,2,..,n}，由m

台相同的机器进行加工处理。作业i所需的处理时间为ti

。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理，任何作业不能拆分成更小的作业。要求：给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

多机调度问题

【分析】：这个问题是一个NP完全问题（(Non-deterministicPolynomial)，即多项式复杂程度的非确定性问题），到目前为止还没有一个有效的解法。对于这一类问题，用贪心选择策略有时可以设计出较好的近似算法。采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。

按此策略，当n<=m时，只要将机器i的[0,ti]时间区间分配给作业i即可。

当n>m时，首先将n个作业依其所需的处理时间从大到小排序，然后依此顺序将作业分配给空闲的处理机。多机调度问题

【例如】设7个独立作业{1,2,3,4,5,6,7}由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别为{2,14,4,16,6,5,3}。用贪心选择策略产生的作业调度如下图所示，所需的加工时间为17。

【问题描述】

键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。输入数据均不需判错,输出应包括所去掉的数字的位置和组成的新的正整数。

删数游戏【算法分析】这是一道运用贪心策略求解的典型问题。在位数固定的前提下，让高位的数字尽量小其值就较小，依据此贪婪策略就可以解决这个问题。怎么样根据贪婪策略删除数字呢？总目标是删除高位较大的数字，具体地相邻两位比较若高位比低位大则删除高位。每次删除一个数字,选择一个使剩下的数最小的数字作为删除对象,之所以选择这样”贪心”的操作,是因为删S个数字的全局最优解包含了删一个数字的子问题的最优解。

删数游戏【例如】N=175438,S=4;可以删去7,5,4,8,得到13。删除S次，每次删的数要使剩下的数尽量小。例如上面的例子，第一次删7,至少比第一次删1,5,4,3,8好！

这样，删数过程是：175438

15438

1438

138

13【算法思想】从左向右找到第一个i,使n[i]>n[i+1]，如果找到了，就删除第i个数字，否则删除删除了若干个最右边的大数字。

删数游戏当S=1时,在N中删除哪一个数字能达到最小的目的?从左到右每相邻的两个数字比较:若出现左边大于右边,则删除左边的大数字.若不出现降序排列,即所有数字全部升序,则删除最右边的大数字.当S>1,按上述操作一个一个删除,删除一个达到最小后,再从头即从串首开始,删除第2个,依次分解为S次完成.若删除不到S个后已无左边大于右边的减序,则停止删除操作,打印剩下串的左边L-S个数字即可(相当于删除了若干个最右边的大数字,这里L为原数字N的位数).

删数游戏#include<iostream>#include<string>usingnamespacestd;intmain(){ stringn;//利用字符串数组保存高精度数字 ints,i,x,m,l;cout<<"inputdataanddeletedatalength:"; cin>>n>>s; i=-1; m=0; x=0;//x统计删除数字的个数 l=n.length(); while(x<s&&m==0) { i++; if(n[i]>n[i+1])//出现递减,删除递减的首数字 {n=n.erase(i,1); x++; i=-1;//从头开始查递减区间 } if(i==1-x-2&&x<s) m=1;//已经无递减区间,循环结束 }

if(x<s)cout<<n.substr(0,l-s+x);//只打印剩下的左边l-(s-x)个数字elsecout<<n<<endl;return0;}运行结果：设计一个算法，把一个真分数表示为埃及分数之和的形式。【问题分析】

所谓埃及分数，是指分子为1的形式。古代埃及有一个非常奇怪的习惯，他们喜欢把一个分数表示为若干个分子为1的分数之和的形式。如：7/8=1/2+1/3+1/24

埃及分数【算法思想】逐步选择分数所包含的最大埃及分数，这些埃及分数之和就是问题的一个解。数学家斐波那契提出的一种求解埃及分数的贪心算法，基本思想是：

(1)设某个真分数