Outline 引入:活动选择问题 贪心法 什么是贪心法 ■贪心法的适用范围 刘培 ■贪心法证明 liupei@pku.edu.cn ■几道习题 活动选择问题 活动选择问题 S={1,2,…,n}为n项活动的集合 ■Si和f分别表示活动开始和结束时间 (1 活动和活动相容当且仅当s>=f或 sj>=fi 思路: ■求两两相容的最大活动集 ■按照结束时间递增序列将活动排序,使得 满足相容关系后,按照标号从小到大选择 活动选择问题 活动选择问题 算法 Greedy select 1. n-length[S]; 2.A-{1} 3.广1; for j-2 to then a·AU{1 贪心法 刘 培 liupei@pku.edu.cn Outline „ 引入：活动选择问题 „ 什么是贪心法 „ 贪心法的适用范围 „ 贪心法证明 „ 几道习题 活动选择问题 „ S={1,2,…,n}为n项活动的集合 „ si和fi分别表示活动i开始和结束时间 (1<=i<=n) „ 活动i和活动j相容当且仅当si>=fj或 sj>=fi „ 求两两相容的最大活动集 活动选择问题 „ 思路： „ 按照结束时间递增序列将活动排序，使得 f1<=f2<=…<=fn „ 满足相容关系后，按照标号从小到大选择 1 2 3 4 5 6 活动选择问题 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 活动选择问题 算法Greedy Select „ 1. n←length[S]; „ 2. A←{1}; „ 3. j←1; „ 4. for i←2 to n „ 5. do if si≥fj „ 6. then A ← A∪{i}; „ 7. j ← i; „ 8. return A