北京大学：《数据结构与算法》课程教学资源（实习课件PPT）贪心法

贪心法 刘培 liupei@pku.edu.cn

贪心法 刘 培 liupei@pku.edu.cn

Outline 引入:活动选择问题 什么是贪心法 贪心法的适用范围 贪心法证明 几道习题

Outline „ 引入：活动选择问题 „ 什么是贪心法 „ 贪心法的适用范围 „ 贪心法证明 „ 几道习题

活动选择问题 S={1,2,n}为n项活动的集合 s和f分别表示活动开始和结束时间 (1<=i<=n) 活动和活动j相容当且仅当s>=f或 SJ>=fi 求两两相容的最大活动集

活动选择问题 „ S={1,2, …,n} 为 n项活动的集合 „ si 和fi分别表示活动i开始和结束时间 (1<=i<=n) „ 活动i和活动 j相容当且仅当si>=fj 或 sj>=fi „ 求两两相容的最大活动集

活动选择问题 思路: 按照结束时间递增序列将活动排序,使得 f<=f2<=.<=fn 满足相容关系后,按照标号从小到大选择

活动选择问题 „ 思路： „ 按照结束时间递增序列将活动排序，使得 f 1<=f 2<= …<=f n „ 满足相容关系后，按照标号从小到大选择 1 2 3 4 5 6

活动选择问题

活动选择问题 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6