搜索
贪心法的基本思想例1:日常生活中经常会碰到找硬币的例子。现有四种硬币，它们的面值分别是1元，5角，1角和1分。现在要给顾客2元1角3分钱。如何找使得所拿出的硬币个数最少?贪心法贪心法将一个最优决策过程变成多步决策过程,并在每步总是做出当前看来是最好的选择。贪心算法并不从全局最优上加以考虑,它所做的选择只是在某种意义上的局部最优选择。例2:如果硬币的币值改为1分,5分,1角1分三种,现要找给顾客1角5分?1个1角1分+4个1分??贪心算法的定义在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。部分背包问题问题描述算法描述算法证明算法分析问题描述问题：给定n种不同物品和一个背包，背包容量为M，物品i的重量是Wi，装物品i的利润是Pi，假定物品i的一部分xi(0≦xi≦1),放进背包,得到利润Pixi问：应该如何装包，才能获得最大利润？问题描述给定M0，Wi0，Pi0，1≦i≦n，要求找一个n元向量(x1,x2,…,xn)，0≦xi≦1，1≦i≦n，使得n∑Pixii=1达到最大，同时满足nΣWixi≦Mi=1算法描述例给定n=3,M=40,(W1,W2,W3)=(28,15,24),(P1,P2,P3)=(35,25,24)。五个可能的解如下：(x1,x2,x3)ΣWixi≦M∑Pixi1(1,4/5,0)4055先装利润最大2(1/2,1,1/3)3750.53(1/28,1,1)4050.25先装重量最小4(5/7,1,5/24)40555(25/28,1,0)4056.25先装利润重量比值最大算法描述背包问题的贪心算法输入：P(1:n),W(1:n),M，按P(i)/W(i)≥P(i+1)/W(i+1)的顺序读入输出：X(1:n)ProcedureGREEDY-KNAPSACKreal:P(1:n),W(1:n),X(1:n),M,CU;Integer:i,n;begin1.Read(P(1:n).W(1:n),M);//设按P(i)/W(i)≥P(i+1)/W(i+1)的顺序读入//2.fori=1tondo3.X(i)=0;//X(i)赋初值//4.CU=M;//CU是背包问题的剩余容量//5.I:=1;6.whileW[I]≤CUdobegin7.X[I]:=1;8.CU:=CU-W[I],9.I:=I+1end;10.X[I]:=CU/W[I]end算法证明定理如果P1/W1≧P2/W2≧…≧Pn/Wn，算法GREEDY_KNAPSACK产生背包问题的一个最优解。证明：设(x1,x2,…,xn)是算法产生的一个解，不失一般性，设存在某个j，1≦j≦n，x1=x2=…=xj-1=1,0≦xj1，xj+1=xj+2=…=xn=0。再设(x1’,x2’,…,xn’)是一个最优解，我们证明(x1’,x2’,…,xn’)＝(x1,x2,…,xn)。若不然，必存在k，1≦k≦n,1≦ik,有xi=xi’，xk≠xk’。于是有两种情况：1xkxk’。此种情况下可得到k-1k-1ΣWixi’+Wkxk’ΣWixi+Wkxk≦Mi=1i=1于是可以通过增大xk’的取值，减小xk+1’,xk+2’,…,xn’的取值，构造优于(x1’,x2’,…,xn’)的解。矛盾。2xkxk’。此种情况下必有xk1。考虑到xi=xi’(1≦ik)，有kk-1ΣWixi=ΣWixi+wkxki=1i=1kk-1ΣWixi’=ΣWixi’+wkxk’i=1i=1所以有：kkΣWixi’ΣWixi=Mi=1i=1说明(x1’,x2’,…,xn’)不是问题的解。矛盾。综合1和2两种情形，算法产生一个最优解。算法分析时间复杂性O(n)空间复杂性O(n)贪心法的基本思想◆一种多步决策方法◆每一步使目标函数值增加最快或最慢◆选择最优化量度是方法的关键贪心算法的基本要素对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。171、贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。2、最优子结构性质动态规划和贪心算法都是一种递推算法均有局部最优解来推导全局最优解不同点：贪心算法：1.贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。2.由（1）中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。动态规划算法：1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解3.边界条件：即最简单的，可以直接得出的局部最优解贪心算法每一步都做目前最好的选择，不考虑下一步的选择。动态规划的子问题每一步求的最优解影响下一个问题的最优解。贪心算法是种策略，思想。。。它并没有固定的模式动态规划的思想是分治+解决冗余把一个复杂的问题分解成一块一块的小问题每一个小问题中得到最优解再从这些最优解中获取更优的答案贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?（例如“0-1背包问题”与“部分背包问题”）3、贪心算法与动态规划算法的差异0-1背包问题给定一个最大载重量为M的卡车和N种动物。已知第i种动物的重量为Wi，其最大价值为Vi，设定M，Wi，Vi均为整数，编程确定一个装货方案，使得装入卡车中的所有动物总价值最大。算法?按贪心法,有反例.设N=3，卡车最大载重量是100，三种动物A、B、C的重量分别是40，50，70，其对应的总价值分别是90、100、150。使用贪心算法的关键：1.该题是否适合于用贪心策略求解2.如何选择贪心标准，以得到问题的最优解例5:排队打水问题2有N个人排队到R个水龙头去打水，他们装满水桶的时间为T1，T2，…，Tn为整数且各不相等，应如何安排他们的打水顺序才能使他们总的花费的时间最少（包括等待时间）？分析由于排队时，越靠前面的计算的次数越多，显然越小的排在越前面得出的结果越小（可以用数学方法简单证明，这里就不再赘述），所以这道题可以用贪心法解答，基本步骤：将输入的时间按从小到大排序；将排序后的时间按顺序依次放入每个水龙头的队列中；统计，输出答案。【例6】设有n个正整数，将他们连接成一排，组成一个最大的多位整数。例如:n=3时，3个整数13,312,343,连成的最大整数为:34331213又如:n=4时,4个整数7,13,4,246连接成的最大整数为7424613输入：NN个数输出:连接成的多位数算法分析：此题很容易想到使用贪心法，但如何贪？整数按从大到小的顺序连接起来，样例符合。再想想，我们还是可以找到反例：12，121应该组成12121而非12112。是不是此题不能用贪心法呢？正确的贪心标准是：先把整数化成字符串，然后再比较a+b和b+a，如果a+bb+a，就把a排在b的前面，反之则把a排在b的后面。删数字问题对给定的n位高精度正整数,去掉其中k(kn)个数字后，按原左右次序将组成一个新的正整数，（1）使得剩下的数字组成的新数最大。（2）使得剩下的数字组成的新数最小？