数据结构与算法实习 算法之三:贪心法 北京大学信息科学技术学院 主讲:张铭、郝丹 zhang lat] net pku. edu.cn http://wwwipkpkueducn/pkujpk/course/siig/shixil 20118 张铭赵海燕王腾蛟宋国杰,《数据结构与算法实验教程》 (国家十一五规划教材),高教社2011年1月
数据结构与算法实习 ——算法之三：贪心法 北京大学信息科学技术学院 主讲：张 铭、郝 丹 mzhang [at] net.pku.edu.cn http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/shixi/ 2011.8 张铭 赵海燕 王腾蛟 宋国杰，《数据结构与算法实验教程》 （国家十一五规划教材），高教社2011年1月
Outline 引入:活动选择问题 贪心法的基本概念 贪心法的适用范围 贪心法证明 ■几道习题
Outline ◼ 引入：活动选择问题 ◼ 贪心法的基本概念 ◼ 贪心法的适用范围 ◼ 贪心法证明 ◼ 几道习题
活动选择问题 nS={12…n}为n项活动的集合 S和f分别表示活动开始和结束时间(1≤i≤n) 活动和活动相容当且仅当s≥f或S12f 相容 不相容 ■目标:求两两相容的最大活动集
活动选择问题 ◼ S={1,2,…,n}为n项活动的集合 ◼ si和fi分别表示活动i开始和结束时间(1 ≤ i ≤ n) ◼ 活动i和活动j相容当且仅当si ≥ fj或sj ≥ fi ◼ 相容 ◼ 不相容 ◼ 目标：求两两相容的最大活动集 1 2 5 6
活动选择问题 ■思路: 按照结束时间递增序列将活动排序,使得 1,6,2,53,4 满足相容关系后,在序列中从左到右选择
活动选择问题 ◼ 思路： ◼ 按照结束时间递增序列将活动排序，使得 f1 ≤ f2 ≤… ≤ fn ◼ 1, 6, 2, 5, 3, 4 ◼ 满足相容关系后，在序列中从左到右选择 1 2 3 4 5 6
活动选择问题
活动选择问题 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6