第五章贪婪法ppt课件.ppt

《第五章贪婪法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章贪婪法5.1贪婪法引言5.2背包问题5.3单源最短路径问题5.4最小花费生成树问题5.5霍夫曼编码问题15.1贪婪法引言一货币兑付问题二贪婪法的设计思想三贪婪法的例子_货郎担问题2一货币兑付问题货币兑付问题：用最少的货币张数支付现金集合表示n张面值为的货币，1in出纳员需支付的现金为A，从P中选取一个最小的子集S，使得用向量表示S中所选取的货币，使得出纳员支付的现金必须满足使得：3货币兑付问题（续）解向量：问题中n个元素的具体取值所构成的向量解空间：问题中n个元素的各种不同取值组合所构成的向量全体约束方程：问题中的限制条件所列出的方程

2、目标函数：问题求解所要达到的目标可行解：满足约束方程的向量最优解：使目标函数达极值的向量4二贪婪法的设计思想1.贪婪法的思想方法2.贪婪法的一般描述3.适于用贪婪法求解的条件51.贪婪法的思想方法不断地从问题的n个元素中选取一个最优的元素的取值，作为局部解向量中的一个分量，使其既满足约束方程，又使目标函数取极值最快，当n个元素的取值均求取之后，解向量就成为完整的向量，它就是问题的解62.贪婪法的一般描述greedy(A,n){solution=;for(i=1;i

3、))solution=union(solution,x);}returnsolution;}73.适于用贪婪法求解的条件1）贪婪选择性质：所求问题的全局最优解，可以通过一系列局部最优的选择来达到例：从10张10元、10张5元、10张1元、10张5角、10张2角、10张1角的货币中兑付57元8角集合顺序表示货币向量表示支付给客户的货币第一步挑出的货币集合，局部解问题简化为在集合中挑选货币、付出47元8角，在以后的步骤中，可以用同样的方法进行挑选，并能得到问题的全局最优解8适于用贪婪法求解的条件（续）2）最优子结构：问题的最优解，包含它的子问题的最优解

4、付给客户的货币集合的最优解是第一步所简化了的子问题的最优解是所以，出纳员付钱问题具有最优子结构性质9三贪婪法的例子_货郎担问题货郎担问题：5个城市，费用矩阵如下总是选择费用最小的路线前进，选择的路线是：143521，总费用是1412345133262373233725423235625310贪婪法的例子_货郎担问题（续）只选择一个城市作为出发城市，所需时间是n个城市都可以作为出发城市，所需时间是从城市1出发的最优的路线是125431，总费用只有131234513326237323372542323562531

5、15.2背包问题一背包问题二思想方法三数据结构四算法描述五算法分析12一背包问题载重量为M的背包，重量为、价值为的物体，1in，把物体装满背包，使背包内的物体价值最大物体可以分割的背包问题，及物体不可分割的背包问题，把后者称为0/1背包问题13二思想方法解向量：：物体被装入背包的部分，：物体没被装入背包；：物体被全部装入背包约束方程：目标函数：选取价值重量比最大的物体装入，既使目标函数的值增加最快，又使背包载重量的消耗较慢14三数据结构typedefstruct{floatp;//n个物体的价值floatw;//n个物体的重量floatv;//

6、n个物体的价值重量比}OBJECT;OBJECTinstance[n];floatx[n];//n个物体装入背包的份量15四算法描述1.floatknapsack_greedy(floatM,OBJECTinstance[],floatx[],intn)2.{inti;4.floatm,p=0;5.for(i=0;i

7、1.for(i=0;i

8、有：(1)假定，算法的最优解是，并且满足(2)18算法分析（续1）若XY，必存在k,对1i