1、贪心法的基本思想贪心法的基本思想例1:日常生活中经常会碰到找硬币的例子。现有四种硬币，它们的面值分别是1元，5角，1角和1分。现在要给顾客2元1角3分钱。如何找使得所拿出的硬币个数最少贪心法贪心法将一个最优决策过程变成多步决策过程,并在每步总是做出当前看来是最好的选择。贪心算法并不从全局最优上加以考虑,它所做的选择只是在某种意义上的局部最优选择。例2:如果硬币的币值改为1分,5分,1角1分三种,现要找给顾客1角5分1个1角1分+4个1分贪心算法的定义在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优
2、解，这种求解方法就是贪心算法。部分背包问题问题描述算法描述算法证明算法分析问题描述问题：给定问题：给定n种不同物品和一个背包，背包容种不同物品和一个背包，背包容量为量为M，物品，物品i的重量是的重量是Wi，装物品，装物品i的利润是的利润是Pi，假定物品，假定物品i的一部分的一部分xi(0xi1),放进放进背包背包,得到利润得到利润Pixi问：应该如何装包，才能获得最大利润？问：应该如何装包，才能获得最大利润？问题描述给定给定M0，Wi0，Pi0，1in，要求找一个，要求找一个n元元向量向量(x1,x2,xn)，0xi1，1in，使得，使得nPixii=1达到最
3、大，同时满足达到最大，同时满足nWixiMi=1算法描述例给定n=3,M=40,(W1,W2,W3)=(28,15,24),(P1,P2,P3)=(35,25,24)。五个可能的解如下：(x1,x2,x3)WixiMPixi1(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)4055(25/28,1,0)4056.25先装利润重量5比值最大算法描述背包问题的贪心算法背包问题的贪心算法输入：输入：P(1:n),W(1:n),M，按，按P(i)
4、/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.whileWICUdobegin7.XI:=1;8.CU:=CU-WI,
5、9.I:=I+1end;10.XI:=CU/WIend算法证明定理定理如果如果P1/W1P2/W2Pn/Wn，算，算法法GREEDY_KNAPSACK产生背包问题的产生背包问题的一个最优解。一个最优解。证明：设证明：设(x1,x2,xn)是算法产生的一个解，不是算法产生的一个解，不失一般性，设存在某个失一般性，设存在某个j，1jn，x1=x2==xj-1=1,0xj1，xj+1=xj+2==xn=0。再设再设(x1,x2,xn)是一个最优解，我们证是一个最优解，我们证明明(x1,x2,xn)(x1,x2,xn)。若不然，必存在若不然，必存在k，
7、复杂性O(n)空间复杂性空间复杂性O(n)贪心法的基本思想一种多步决策方法一种多步决策方法每一步使目标函数值增加最快或最慢每一步使目标函数值增加最快或最慢选择最优化量度是方法的关键选择最优化量度是方法的关键贪心算法的基本要素对于一个具体的问题，怎么知道是否可用对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最贪心算法解此问题，以及能否得到问题的最优解呢优解呢这个问题很难给予肯定的回答。这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有题中看到这类问题一般具有22个重要的性质：个重要的性
8、质：贪心选择性质贪心选择性质和和最优子结构性质最优子结构性质。1711、贪心选择性质、贪心选择性质所谓所谓贪心选择性质贪心选择性质是指所求问题的是指所求问题的整体最整体最优解优解可以通过一系列可以通过一系列局部最优局部最优的选择，即贪心的选择，即贪心选择来达到。这是贪心算法可行的第一个基本选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区要素，也是贪心算法与动态规划算法的主要区别。别。对于一个具体问题，要确定它是否具有贪对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优
9、解。最终导致问题的整体最优解。当一个问题的最优解包含其子问题的当一个问题的最优解包含其子问题的最优解时，称此问题具有最优解时，称此问题具有最优子结构性质最优子结构性质。问题的最优子结构性质是该问题可用动态问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征规划算法或贪心算法求解的关键特征。22、最优子结构性质、最优子结构性质动态规划和贪心算法都是一种递推算法均有局部最优解来推导全局最优解不同点：贪心算法：1.贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。2.由（1）中的介绍，可以知道贪
10、心法正确的条件是：每一步的最优解一定包含上一步的最优解。动态规划算法：1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解3.边界条件：即最简单的，可以直接得出的局部最优解贪心算法每一步都做目前最好的选择，不考虑下一步的选择。动态规划的子问题每一步求的最优解影响下一个问题的最优解。贪心算法是种策略，思想。它并没有固定的模式动态规划的思想是分治+解决冗余把一个复杂的问题分解成一块一块的小问题每一个小问题中得到最优解再从这些最优解中获取更优的答案贪心算法和动态规划算法都
11、要求问题具贪心算法和动态规划算法都要求问题具有最优子结构性质，这是有最优子结构性质，这是22类算法的一个类算法的一个共同点。但是，对于具有共同点。但是，对于具有最优子结构最优子结构的问的问题应该选用贪心算法还是动态规划算法求题应该选用贪心算法还是动态规划算法求解解是否能用动态规划算法求解的问题也是否能用动态规划算法求解的问题也能用贪心算法求解能用贪心算法求解（例如“0-1背包问题”与“部分背包问题”）3、贪心算法与动态规划算法的差异0-1背包问题给定一个最大载重量为M的卡车和N种动物。已知第i种动物的重量为Wi，其最大价值为Vi，设定M，Wi，Vi均为整数，编程确定一个装货方