《算法第4章-第5讲-贪心法(2).》由会员分享，可在线阅读，更多相关《算法第4章-第5讲-贪心法(2).（37页珍藏版）》请在金锄头文库上搜索。
1、 计算机科学学院 王小明 （博士/教授/博士生导师） Email: wangxm 每节一经典 对大问题求解：“局部最优到全局最优” “走一步看一步，步步追求最优” 回顾：哪些问题适合用“贪心法”获得的最优解？ 满足：贪心选择性质、最优子结构性质 的问题适合用“贪心法” 求 最优解 那么，何谓贪心选择性质、最优子结构性质 ？ 1.贪心选择性质 所求问题的整体最优解可以通过一系列局部最优解的选择，即 “贪心选择”来得到。 2.最优子结构性质 当一个问题的最优解包含其所有子问题的最优解时，称此问题具 有最优子结构性质。 第5讲 贪心算法 可绝对贪婪问题 例12.数列级差问题。数列级差问题。 在黑板上
2、写了n个正整数排成的一个数列，进行如下 操作：每一次擦去其中的两个数a和b，然后在数列中 加入一个数ab+1，如此下去直至黑板上剩下一个数 为止，在所有按这种操作方式最后得到的数中，最大 的记为max，最小的记为为min，则该数列的极差定义 为M=max-min。 第5讲 贪心算法 问题理解：用9以内实例理解（经典）当n=3时，我们 来讨论，以3，5，7为例 3 5 716 7113 去掉16，7 添加 113 去掉3，5 添加 16 去掉3，5 添加 16 去掉3，5 添加 16 3 5 722 5111 去掉22，5 添加 111 去掉3，7 添加 22 3 5 736 3109 去掉36
3、，3 添加 109 去掉5，7 添加 36 从上面不难发现：先去掉小数据得到的是最大值 先去掉大数据得到的是最小值 第5讲 贪心算法 n 问题分析：下面用3个数为例来说明贪心策略的合理性 ，不防设：ab c,表示为： b=a+k1，c=a+k1+k2 则计算结果为： 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大于3时，我们可经过n-3次变换后得到3个数。显然此问题 适合
4、贪婪策略。求最大数的时候操作较小数；求最小数的时候 操作较大数。 第5讲 贪心算法 算法设计思想： 由上述我们可以得到启发：从现有的数据中，选取最 大和最小的两个数，计算后的结果继续参加运算，直 到最后剩余一个为止。 求max和min的过程必须独立，否则将不能找到最大和 最小数。 第5讲 贪心算法 step1 输入：数据序列1，数据序列2， 并且：数据序列1=数据序列1，即两个序列相同 step2 对数据序列1操作：寻找最大数 max： 通过排序法找到当前数列中较小的两个数s1，s2； 删除s1，s2； 把s1s2+1存到删除后的数列中；重复执行，直到 只剩一个数 Step3 对数据序列1操作
5、：寻找最小数 min： 通过排序法找到当前数列中较大的两个数s1，s2； 删除s1，s2； 把s1s2+1存到删除后的数列中；重复执行，直到 只剩一个数 Step4 输出结果：max-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种币值 设置数组s，统计7 种币
6、值使用张数 利用贪心策略完成 工资的分发（尽量 取大面额币种） 输出工资的分发过 程中需要的不同币 值的张数 第5讲 贪心算法 算法分析： 时间复杂度分析 Step2. 依贪心选择策略,将尽可能多的单位重量价值 最高的物品装入背包.若将这种物品全部装入 背包后,背包内的物品总重量未超过M,则选择 单位重量价值次高的物品并尽可能多地装入背 包； Step3. 依此策略循环执行,直到背包装满为止。 第5讲 贪心算法 第5讲 贪心算法 算法实现(编码)： greedy-knapsack (float valuen, weightn, W) float xn, LW; / LW背包的剩余重量 Sort
7、(valuen/weightn); /价值/重量比值按从大到小排序 for( int i=1; i =n; i +) xi=0; / xi的值来表示物体i是否放入背包 i=1;LW=W; /初始背包重量为W while (weighti=LW) xi=1; /如果当前物品可以放入则为1 LW=LW-weighti;/背包可容纳剩余重量 i+; xi=LW/weighti;/不能整体装入时，部分装入包中 第5讲 贪心算法 算法分析： 算法knapsack的主要计算时间在于将各种物品依其 单位重量的价值从大到小排序。因此，算法的计算 时间上界为O(nlogn)。 当然，为了证明算法的正确性，还必须
8、证明背包问 题具有贪心选择性质。 学有余力的同学试证明上述性质。 n背包问题只有一种限制,即背包所能承受的 重量(即重量不能超过M kg），但是实际上 背包除受重量的限制外,还有体积的限制,这 就是不但要求旅行者的背包的重量c不能超 过M kg,还要求背包的体积v不能超过V m3, 等多种类似的约束，我们把这样的问题称为 “多维背包问题”。 扩 展 多维背包问题 n m 个约束,其中每一个约束条件被称为一个背包约束, 因此多维背包问题也被称为m-维背包问题. n 多维背包问题(MKP)是个著名的NP-难问题。 多维背包问题 数学模型 第5讲 贪心算法 第5讲 贪心算法 小 结： n利用贪心策略
9、解题，需要解决两个问题： 首先，确定问题是否能用贪心策略求解;一般来说, 适用于贪心策略求解的问题具有以下特点： 可通过局部的贪心选择来达到问题的全局最优 解.运用贪心策略解题,一般来说需要一步步的进行多 次的贪心选择.在经过一次贪心选择之后,原问题将变 成一个相似的,但规模更小的问题,而后的每一步都是 当前看似最佳的选择,且每一个选择都仅做一次. 原问题的最优解包含子问题的最优解,即问题具 有最优子结构的性质.在背包问题中，第一次选择单位 质量最大的货物,它是第一个子问题的最优解,第二次选 择剩下的货物中单位重量价值最大的货物,同样是第二 个子问题的最优解,依次类推。 其次,如何选择一个贪心
10、策略标准？正确的贪心策略 可以得到问题的最优解,在确定采用贪心算法解决问题时 ,不能随意的判断贪心策略标准是否正确,尤其不要被表 面上看似正确的贪心策略标准所迷惑.在得出贪心策略标 准之后应给予严格的数学证明（通常比较困难）。 第5讲 贪心算法 课堂讨论提纲： 1. 结合典型的问题实例，讨论迭代算法、蛮力 算法、分治算法、贪婪算法解决问题的基本 思想框架。 2. 递归技术（方法）与上述算法之间的关系和 区别，为什么没有单独的“递归算法策略”？ 3. 分析一个算法的时间复杂度的关键思想和步 骤。 4. 用“计算思维”解决问题的基本步骤。 第5讲 贪心算法 本节作业： 预习：p166- p185 ,动态规划 第5讲 贪心算法 Thats all for today See you next time Good bye!
