c语言程序设计——贪心算法

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(0 xi 1),放进放进背包背包,得到利润得到利润Pi xi 问：应该如何装包，才能获得最大利润？问：应该如何装包，才能获得最大利润？问题描述给定给定M0，Wi0，Pi0， 1 i n，要求找一个，要求找一个n元元向量向量(x1,x2,xn)， 0 xi 1， 1 i n，使得，使得 n Pixi i=1达到最

3、大，同时满足达到最大，同时满足 n WixiM i=1 算法描述例 给定n=3,M=40, (W1,W2,W3)= (28,15,24), (P1,P2,P3)=(35,25,24)。五个可能的解如下： (x1,x2,x3) WixiM Pixi1 (1,4/5,0) 40 55 先装利润最大2 (1/2,1,1/3) 37 50.53 (1/28,1,1) 40 50.25 先装重量最小4 (5/7,1,5/24) 40 55(25/28,1,0) 40 56.25 先装利润重量5 比值最大算法描述背包问题的贪心算法背包问题的贪心算法输入：输入：P(1:n),W(1:n),M，按，按P(i)

4、/W(i) P(i+1)/W(i+1)的顺序读入的顺序读入输出：输出：X(1:n)Procedure GREEDY-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.for i=1 to n do3. X(i)=0;/X(i)赋初值赋初值/4.CU=M;/CU是背包问题的剩余容量是背包问题的剩余容量/5.I:=1;6.while WI CU do begin7. XI:=1;8. CU:=CU-WI,

5、9. I:=I+1 end;10.XI:=CU/WIend算法证明定理定理 如果如果P1/W1 P2/W2 Pn/Wn ，算，算法法 GREEDY_ KNAPSACK 产生背包问题的产生背包问题的一个最优解。一个最优解。证明：设证明：设(x1,x2,xn)是算法产生的一个解，不是算法产生的一个解，不失一般性，设存在某个失一般性，设存在某个j，1jn， x1 = x2 = = xj-1=1, 0 xj1， xj+1 = xj+2 = = xn =0。再设再设(x1,x2,xn)是一个最优解，我们证是一个最优解，我们证明明(x1,x2,xn) (x1,x2,xn)。若不然，必存在若不然，必存在k，

6、1kn, 1i xk 。此种情况下可得到。此种情况下可得到 k-1 k-1 Wixi+ Wkxk Wixi + Wkxk M i=1 i=1于是可以通过增大于是可以通过增大xk 的取值，减小的取值，减小xk+1, xk+2, xn的取值，构造优于的取值，构造优于(x1, x2,xn)的解。矛盾。的解。矛盾。2 xk xk 。此种情况下必有。此种情况下必有xk 1。考虑到考虑到xi = xi (1i Wixi =M i=1 i=1说明说明 (x1, x2,xn)不是问题的解。矛盾。不是问题的解。矛盾。综合综合1和和2两种情形，算法产生一个最优解两种情形，算法产生一个最优解。算法分析时间复杂性时间

7、复杂性 O(n)空间复杂性空间复杂性 O(n)贪心法的基本思想一种多步决策方法一种多步决策方法每一步使目标函数值增加最快或最慢每一步使目标函数值增加最快或最慢选择最优化量度是方法的关键选择最优化量度是方法的关键贪心算法的基本要素 对于一个具体的问题，怎么知道是否可用对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最贪心算法解此问题，以及能否得到问题的最优解呢优解呢? ?这个问题很难给予肯定的回答。这个问题很难给予肯定的回答。 但是，从许多可以用贪心算法求解的问但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有题中看到这类问题一般具有2 2个重要的性质：个重要的性

8、质：贪心选择性质贪心选择性质和和最优子结构性质最优子结构性质。 171 1、贪心选择性质、贪心选择性质 所谓所谓贪心选择性质贪心选择性质是指所求问题的是指所求问题的整体最整体最优解优解可以通过一系列可以通过一系列局部最优局部最优的选择，即贪心的选择，即贪心选择来达到。这是贪心算法可行的第一个基本选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区要素，也是贪心算法与动态规划算法的主要区别。别。 对于一个具体问题，要确定它是否具有贪对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优

9、解。最终导致问题的整体最优解。 当一个问题的最优解包含其子问题的当一个问题的最优解包含其子问题的最优解时，称此问题具有最优解时，称此问题具有最优子结构性质最优子结构性质。问题的最优子结构性质是该问题可用动态问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征规划算法或贪心算法求解的关键特征。 2 2、最优子结构性质、最优子结构性质动态规划和贪心算法都是一种递推算法 均有局部最优解来推导全局最优解 不同点： 贪心算法： 1.贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。 2.由（1）中的介绍，可以知道贪

10、心法正确的条件是：每一步的最优解一定包含上一步的最优解。动态规划算法： 1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解 3.边界条件：即最简单的，可以直接得出的局部最优解贪心算法每一步都做目前最好的选择，不考虑下一步的选择。动态规划的子问题每一步求的最优解影响下一个问题的最优解。贪心算法是种策略，思想。它并没有固定的模式动态规划的思想是分治+解决冗余把一个复杂的问题分解成一块一块的小问题每一个小问题中得到最优解再从这些最优解中获取更优的答案 贪心算法和动态规划算法都

11、要求问题具贪心算法和动态规划算法都要求问题具有最优子结构性质，这是有最优子结构性质，这是2 2类算法的一个类算法的一个共同点。但是，对于具有共同点。但是，对于具有最优子结构最优子结构的问的问题应该选用贪心算法还是动态规划算法求题应该选用贪心算法还是动态规划算法求解解? ?是否能用动态规划算法求解的问题也是否能用动态规划算法求解的问题也能用贪心算法求解能用贪心算法求解? ?（例如“0-1背包问题”与“部分背包问题”）3、贪心算法与动态规划算法的差异 0-1背包问题 给定一个最大载重量为M的卡车和N种动物。已知第i种动物的重量为Wi，其最大价值为Vi，设定M，Wi，Vi均为整数，编程确定一个装货方

12、案，使得装入卡车中的所有动物总价值最大。算法?按贪心法,有反例.设N=3，卡车最大载重量是100，三种动物A、B、C的重量分别是40，50，70，其对应的总价值分别是90、100、150。使用贪心算法的关键：使用贪心算法的关键： 该题是否适合于用贪心策略求解 如何选择贪心标准，以得到问题的最优解例5: 排队打水问题2有N个人排队到R个水龙头去打水，他们装满水桶的时间为T1，T2，Tn为整数且各不相等，应如何安排他们的打水顺序才能使他们总的花费的时间最少（包括等待时间）？分析分析 由于排队时，越靠前面的计算的次数越多，由于排队时，越靠前面的计算的次数越多，显然越小的排在越前面得出的结果越小显然越

13、小的排在越前面得出的结果越小（可以用数学方法简单证明，这里就不再（可以用数学方法简单证明，这里就不再赘述），所以这道题可以用贪心法解答，赘述），所以这道题可以用贪心法解答，基本步骤：基本步骤：将输入的时间按从小到大排序；将输入的时间按从小到大排序；将排序后的时间按顺序依次放入每个水龙头的队将排序后的时间按顺序依次放入每个水龙头的队列中；列中； 统计，输出答案。统计，输出答案。【例例6】设有n个正整数，将他们连接成一排，组成一个最大的多位整数。例如:n=3时，3个整数13,312,343,连成的最大整数为:34331213又如:n=4时,4个整数7,13,4,246连接成的最大整数为7424613输入：N N个数输出:连接成的多位数算法分析：此题很容易想到使用贪心法，但如何贪？整数按从大到小的顺序连接起来，样例符合。再想想，我们还是可以找到反例：12，121 应该组成12121而非12112。是不是此题不能用贪心法呢？正确的贪心标准是：先把