Activity Selection Problem Suppose we have a set S=fa,a2.... of n proposed activities that wish to use a resource,such as a lecture hall,which can serve only one activity at a time.Each activity a has a start time s and a finish timefi,wheres<f<o.If selected,activity ai takes place during the half-open time interval [)Activitiesa and a are compatible if the intervals [s)and [sj,)do not overlap.That is,a;and aj are compatible if si or sj In the activity-selection problem,we wish to select a maximum-size subset of mutually compatible activities. 一个样本输入: 5678 10 8 8 2 11 14 6
Activity Selection Problem 一个样本输入:
S表示开始时间不早于活动a的结束时间,而 结束时间早于α的结束时间的所有活动的集合。 If we denote the size of an optimal solution for the set S by ci,j],then we would have the recurrence ci,j川=ci,k]+c[k,j川+1 假设我们知道其中包含活动ak。 S,中最多相互兼容的活动数 0 c,小=} if Sij=0 max{c[i,k]+c[k,门+l}ifS≠0 kESij
Sij表示开始时间不早于活动ai的结束时间,而 结束时间早于aj的结束时间的所有活动的集合。 Sij中最多相互兼容的活动数 假设我们知道其中包含活动ak
动态规划解法 在上述递归关系中,4,可以是S中任一活动,每选定一个特 定的a,则确定特定的子问题。 动态规划方法按照合适的次序 解所有的子问题。 问题3: 是否有可能不必解所 有的子问题?
动态规划解法 在上述递归关系中,ak可以是Sij中任一活动,每选定一个特 定的ak , 则确定特定的子问题。动态规划方法按照合适的次序 解所有的子问题
Activity Selection:the Idea 要解的问题用Sk={a;∈S:≥}表示,S是原始问题所给的 所有活动的集合,则原始问题为S: ■ Greedy方法: 口选择完成时间最早的活动,假设是a; 口解子问题S1 Greedy可以指不同的“最”,但有的“最” 可以得到正确的解,有的“最”却未必!
Activity Selection: the Idea ◼ 要解的问题用 表示,S是原始问题所给的 所有活动的集合,则原始问题为S0 ; ◼ Greedy方法: ❑ 选择完成时间最早的活动,假设是a1 ; ❑ 解子问题S1。 Greedy可以指不同的“最”,但有的“最” 可以得到正确的解,有的“最”却未必!