算法第4章-第5讲-贪心法(2)

1、 计算机科学学院 王小明 （博士博士/ /教授教授/ /博士生导师博士生导师） Email: 每节一经典每节一经典 对大问题求解：对大问题求解：“局部最优到全局最优局部最优到全局最优” “走一步看一步，步步追求最优走一步看一步，步步追求最优” 回顾：哪些问题适合用回顾：哪些问题适合用“贪心法贪心法”获得的最优解？获得的最优解？ 满足：满足：贪心选择性质、最优子结构性质贪心选择性质、最优子结构性质 的问题适合用的问题适合用“贪心法贪心法” 求求 最优解最优解 那么，何谓那么，何谓贪心选择性质、最优子结构性质贪心选择性质、最优子结构性质 ？ 1.1.贪心选择性质贪心选择性质 所求问题的所求问题的整

2、体最优解整体最优解可以通过一系列可以通过一系列局部最优解局部最优解的选择，即的选择，即 “ “贪心选择贪心选择”来得到。来得到。 2.2.最优子结构性质最优子结构性质 当一个问题的最优解包含其所有子问题的最优解时，称此问题具当一个问题的最优解包含其所有子问题的最优解时，称此问题具 有有最优子结构性质最优子结构性质。 第5讲 贪心算法 可绝对贪婪问题可绝对贪婪问题 例例1212. . 在黑板上写了在黑板上写了n n个正整数排成的一个数列，进行如下个正整数排成的一个数列，进行如下 操作：每一次擦去其中的两个数操作：每一次擦去其中的两个数a a和和b b，然后在数列中，然后在数列中 加入一个数加入一

3、个数a ab+1b+1，如此下去直至黑板上剩下一个数，如此下去直至黑板上剩下一个数 为止，在所有按这种操作方式最后得到的数中，最大为止，在所有按这种操作方式最后得到的数中，最大 的记为的记为maxmax，最小的记为为，最小的记为为minmin，则该数列的极差定义，则该数列的极差定义 为为M=max-minM=max-min。 第5讲 贪心算法 问题理解：用问题理解：用9 9以内实例理解（经典）当以内实例理解（经典）当n=3n=3时，我们时，我们 来讨论，以来讨论，以3 3，5 5，7 7为例为例 3 5 716 7113 去掉16，7 添加 113 去掉3，5 添加 16 去掉3，5 添加 1

4、6 去掉3，5 添加 16 3 5 722 5111 去掉22，5 添加 111 去掉3，7 添加 22 3 5 736 3109 去掉36，3 添加 109 去掉5，7 添加 36 从上面不难发现：先去掉从上面不难发现：先去掉小数据小数据得到的是得到的是最大值最大值 先去掉先去掉大数据大数据得到的是得到的是最小值最小值 第5讲 贪心算法 n 问题分析：下面用问题分析：下面用3 3个数为例来说明贪心策略的合理性，个数为例来说明贪心策略的合理性， 不防设：不防设：a ab b c,c,表示为：表示为： b=a+kb=a+k1 1，c=a+kc=a+k1 1+k+k2 2 则计算结果为：则计算结果

5、为： l (ab+1)c+1 =a3+(2k1+k2) a2+(k12+k1k2)a+k1+k2+1 l (ab+1)c+1 =a3+(2k1+k2)a2+(k12+k1k2)a+k1+1 l (ab+1)c+1 =a3+(2k1+k2)a2+(k12+k1k2)a+1 当当n n大于大于3 3时，我们可经过时，我们可经过n-3n-3次变换后得到次变换后得到3 3个数。显然此问题个数。显然此问题 适合贪婪策略。求最大数的时候操作较小数；求最小数的时候适合贪婪策略。求最大数的时候操作较小数；求最小数的时候 操作较大数。操作较大数。 第5讲 贪心算法 算法设计思想：算法设计思想： 由上述我们可以得

6、到启发：从现有的数据中，选取最由上述我们可以得到启发：从现有的数据中，选取最 大和最小的两个数，计算后的结果继续参加运算，直大和最小的两个数，计算后的结果继续参加运算，直 到最后剩余一个为止。到最后剩余一个为止。 求求maxmax和和minmin的过程必须独立，否则将不能找到最大和的过程必须独立，否则将不能找到最大和 最小数。最小数。 第5讲 贪心算法 step1 step1 输入：数据序列输入：数据序列1 1，数据序列，数据序列2 2， 并且：并且：数据序列数据序列1=1=数据序列数据序列1 1，即两个序列相同，即两个序列相同 step2 step2 对数据序列对数据序列1 1操作：寻找最大

7、数操作：寻找最大数 maxmax： 通过排序法找到当前数列中较小的两个数通过排序法找到当前数列中较小的两个数s1s1，s2s2； 删除删除s1s1，s2s2； 把把s1s1s2+1s2+1存到删除后的数列中；重复执行，直到存到删除后的数列中；重复执行，直到 只剩一个数只剩一个数 Step3 Step3 对数据序列对数据序列1 1操作：操作：寻找最小数寻找最小数 minmin： 通过排序法找到当前数列中较大的两个数通过排序法找到当前数列中较大的两个数s1s1，s2s2； 删除删除s1s1，s2s2； 把把s1s1s2+1s2+1存到删除后的数列中；重复执行，直到存到删除后的数列中；重复执行，直到

8、 只剩一个数只剩一个数 Step4 Step4 输出结果：输出结果：max-minmax-min 算法描述：算法描述： 详细如下详细如下 第5讲 贪心算法 算法分析：算法分析： 时间复杂度分析时间复杂度分析 算法中的主要操作就是比较查找和计算，计算法中的主要操作就是比较查找和计算，计 算是线性的，而比较操作接近算是线性的，而比较操作接近n2 for(i=1;i=n;i=i+1) input(GZ); for(j=1;j7;j=j+1) A=GZ/Bj; Sj=Sj+A; GZ=GZ-A*Bj; for(i=1;i=7;i=i+1) print(Bi,”-”,si); 预存预存7 7种币值种币值

9、 设置数组设置数组s s，统计，统计7 7 种币值使用张数种币值使用张数 利用贪心策略完成利用贪心策略完成 工资的分发（尽量工资的分发（尽量 取大面额币种）取大面额币种） 输出工资的分发过输出工资的分发过 程中需要的不同币程中需要的不同币 值的张数值的张数 第5讲 贪心算法 算法分析：算法分析： 时间复杂度分析时间复杂度分析 ; Step2. Step2. 依贪心选择策略依贪心选择策略, ,将尽可能多的将尽可能多的单位重量价值单位重量价值 最高最高的物品装入背包的物品装入背包. .若将这种物品全部装入若将这种物品全部装入 背包后背包后, ,背包内的物品总重量未超过背包内的物品总重量未超过M,M

10、,则选择则选择 单位重量价值次高的物品单位重量价值次高的物品并尽可能多地装入背并尽可能多地装入背 包；包； Step3. Step3. 依此策略依此策略循环执行循环执行, ,直到背包装满为止。直到背包装满为止。 第第5 5讲讲 贪心算法贪心算法 第第5 5讲讲 贪心算法贪心算法 算法实现算法实现(编码编码)： greedy-knapsack (float valuen, weightn, W) float xn, LW; / LWLW背包的剩余重量背包的剩余重量 Sort(valuen/weightn); /价值价值/重量比值按从大到小排序重量比值按从大到小排序 for( int i=1; i

11、 =n; i +) xi=0; / xi的值来表示的值来表示物体物体i i是否放入背包是否放入背包 i=1; i=1;LW=WLW=W; /初始背包重量为初始背包重量为W while (weighti=LW) xi=1; /如果当前物品可以放入则为如果当前物品可以放入则为1 LW=LW-weighti;/背包可容纳剩余重量背包可容纳剩余重量 i+; xi=LW/weighti;/不能整体装入时，部分装入包中不能整体装入时，部分装入包中 第第5 5讲讲 贪心算法贪心算法 算法分析：算法分析： 算法算法knapsack的主要计算时间在于将各种物品依其的主要计算时间在于将各种物品依其 单位重量的价值

12、从大到小排序。因此，算法的计算单位重量的价值从大到小排序。因此，算法的计算 时间上界为时间上界为O(nlogn)。 当然，为了证明算法的正确性，还必须证明背包问当然，为了证明算法的正确性，还必须证明背包问 题具有贪心选择性质题具有贪心选择性质。 学有余力的同学试证明上述性质。 n背包问题只有一种限制背包问题只有一种限制, ,即背包所能承受的重即背包所能承受的重 量量( (即重量不能超过即重量不能超过M M kgkg），但是实际上背包），但是实际上背包 除受重量的限制外除受重量的限制外, ,还有体积的限制还有体积的限制, ,这就是这就是 不但要求旅行者的背包的重量不但要求旅行者的背包的重量c c

13、不能超过不能超过M M kgkg, ,还要求背包的体积还要求背包的体积v v不能超过不能超过V V m m3 3, ,等多种等多种 类似的约束，我们把这样的问题称为类似的约束，我们把这样的问题称为“多维多维 背包问题背包问题”。 扩扩 展展 多维背包问题多维背包问题 n1,2,i0,1x m1,2,jbxrs.t. xpmax ij j n 1i ijij i n 1i i n m m 个约束个约束, ,其中每一个约束条件被称为一个背包约束其中每一个约束条件被称为一个背包约束, , 因此多维背包问题也被称为因此多维背包问题也被称为m-m-维背包问题维背包问题. . n 多维背包问题多维背包问题

14、(MKP)(MKP)是个著名的是个著名的NP-NP-难问题。难问题。 多维背包问题多维背包问题 数学模型数学模型 第第5 5讲讲 贪心算法贪心算法 第第5 5讲讲 贪心算法贪心算法 小小 结：结： n利用贪心策略解题，需要解决两个问题：利用贪心策略解题，需要解决两个问题： 首先，确定问题是否能用贪心策略求解首先，确定问题是否能用贪心策略求解; ;一般来说一般来说, , 适用于贪心策略求解的问题具有以下特点：适用于贪心策略求解的问题具有以下特点： 可通过局部的贪心选择来达到问题的全局最优可通过局部的贪心选择来达到问题的全局最优 解解. .运用贪心策略解题运用贪心策略解题, ,一般来说需要一步步的

15、进行多一般来说需要一步步的进行多 次的贪心选择次的贪心选择. .在经过一次贪心选择之后在经过一次贪心选择之后, ,原问题将变原问题将变 成一个相似的成一个相似的, ,但规模更小的问题但规模更小的问题, ,而后的每一步都是而后的每一步都是 当前看似最佳的选择当前看似最佳的选择, ,且每一个选择都仅做一次且每一个选择都仅做一次. . 原问题的最优解包含子问题的最优解原问题的最优解包含子问题的最优解, ,即问题具即问题具 有最优子结构的性质有最优子结构的性质. .在背包问题中，在背包问题中，第一次第一次选择单位选择单位 质量最大的货物质量最大的货物, ,它是第一个子问题的最优解它是第一个子问题的最优

16、解, ,第二次第二次选选 择剩下的货物中单位重量价值最大的货物择剩下的货物中单位重量价值最大的货物, ,同样是第二同样是第二 个子问题的最优解个子问题的最优解, ,依次类推。依次类推。 其次其次,如何选择一个贪心如何选择一个贪心策略策略标准？正确的贪心标准？正确的贪心策略策略 可以得到问题的最优解可以得到问题的最优解,在确定采用贪心算法解决问题在确定采用贪心算法解决问题 时时,不能随意的判断贪心不能随意的判断贪心策略标准策略标准是否正确是否正确,尤其不要被尤其不要被 表面上看似正确的贪心表面上看似正确的贪心策略标准策略标准所迷惑所迷惑.在得出贪心在得出贪心策策 略标准略标准之后应给予严格的数学证明（之后应给予严格的数学证明（通常比较困难通常比较困难）。）。 第第5 5讲讲 贪心算法贪心算法 课堂讨论提纲：课堂讨论提纲： 1. 结合典型的问题实例，讨论迭代算法、蛮力结合典型的问题实例，讨论迭代算法、蛮力 算法、分治算法、贪婪算法解决问题的基本算法、分治算法、贪婪算法解决问题的基本 思想框架。思想框架。 2. 递归技术（方法）与上述算法之间的关系和递归技术（方法）与上述算法之间的关系和 区别，为什么没有单独的区别，为什么没有单独的