算法设计与分析_第4章_贪心算法1.pdf
文本预览下载声明
算法设计与分析
第4章贪心算法
(1)
1
学习要点
理解贪心算法的概念
掌握贪心算法的基本要素
(1 )最优子结构性质
(2 )贪心选择性质
理解贪心算法不动态规划算法的差异
理解贪心算法的一般理论
2
学习要点
通过应用范例学习贪心设计策略
(1 )活动安排问题;
(2 )最优装载问题;
(3 )哈夫曼编码;
(4 )单源最短路徂;
(5 )最小生成树;
3
引言
Similar to dynamic programming. Used for
optimization problems.
Optimization problems typically go through a
sequence of steps, with a set of choices at each
step.
For many optimization problems, using
dynamic programming to determine the best
choices is overkill (过度的杀伤威力).
贪心算法: Simpler, more efficient
4
4
引言
应用
找钱
四种硬币:1分,5分,1角,2角5分
找六角3分,怎么给?
排队时出现拥挤情况,如何做才能节省用户
时间?
5
引言
研究
朱为鹏,高成英,罗笑南.全局各向异性四边形主导网
格重建方法.软件学报,2012,23(5):1305-1314
叶齐祥,焦建彬,蒋树强.基于多尺度方向特征的快速
鲁棒人体检测算法.软件学报,2011,22(12):3004-3014
程卫芳,廖湘科,沈昌祥.有向传感器网络最大覆盖调
度算法.软件学报,2009,20(4):975-984
刘勇,高宏,李建中.基于联合意义度量的Top-K图模
式挖掘.计算机学报,2010,2期:215-230
张海英,温玄,张田文.低信噪比多目标检测的贪心算
法. 计算机学报,2008,1期:142-150
崔鹏,刘红静.测试集问题的集合覆盖贪心算法的深
入近似.软件学报,2006,17(7):1494-1500 6
引言-实例
0-1背包问题
n 个物品, 物品i 价值vi ,重wi
背包的最大负载量为W ,如何选取物品,使
得背包装的物品价值最大
每个物品是一个整体,丌能分割,因此,要
么选取该物品,要么丌选取
(分数)背包问题
Like the 0-1 knapsack problem, 但是可以取
走物品的一部分.
7
引言-实例
实例
显示全部