Mathematical model Definition of solution Each activity a; has a start time S, and a subset a of s is a solution if all the finish time f where0≤sf<∝ activities in A are mutually compatible · Compatible【相容】 activities: We call two We call a solution A is optimal if it is a activities are compatible if the two intervals does not overlap (i.e, ai, a, are compatible solution whose size is one of the largest is≥fors ·S={a1,a2…an} Problem: The activity-selection problem is to select a maximum- size subset of s ctivities An instance of the problem 按照动态规划步骤分析 S={14).[35),[0.6),[57).[3.8),[59) 1.选择:选什么?我们选择必定有一个活动在 最优解中假设其为ak [6,10),[8,11),8,12,[2,13),[1214) 2.子问题空间, Let ax be in the optimal solution, how to construct the sub-problem paces?第一部分:在a开始前结束的活动 Notice! The elements are sorted by the 成的问题,第二部分:在a结束后开始的 end time 活动构成的问题,最优解由第一部分的最优 解十{a}+第二部分的最优解。 3.正确吗?如果有一个最优解,从中取出 活动,而后把此最优解分成两部分,问其 的第一部分是第一个子问题的最优解吗? 最优子问题 人工活动 根据上面的分析我们构造以下子问题: Adding two fictitious activities ao and an+1 LetS= (ak in S:f≤sfk≤ si, then Si is the such that fo=0 and Sn+1 = oo, then S=So.n+1 subset of s that can start after activity a ·原问题S=Sont! finishes and finish before activity a starts 原问题是什么?2 清华大学 软件学院 宋斌恒 7 Mathematical model •Each activity ai has a start time si and finish time f i , where 0≤si<f i<∞. • Compatible【相容】 activities: We call two activities are compatible if the two intervals does not overlap (i.e., ai , aj are compatible if si≥f j or sj≥f i ) • S={a1 ,a2 ,… ,an } • Problem: The activity-selection problem is to select a maximum-size subset of S contains mutually compatible activities 清华大学 软件学院 宋斌恒 8 Definition of Solution •A subset A of S is a solution if all the activities in A are mutually compatible. •We call a solution A is optimal if it is a solution whose size is one of the largest. 清华大学 软件学院 宋斌恒 9 An instance of the problem •S={[1,4), [3,5), [0,6), [5,7), [3,8), [5,9), [6,10), [8,11), [8,12), [2,13), [12,14)} •Notice! The elements are sorted by the end time 清华大学 软件学院 宋斌恒 10 按照动态规划步骤分析 1. 选择：选什么？我们选择必定有一个活动在 最优解中,假设其为ak 2. 子问题空间，Let ak be in the optimal solution, how to construct the sub-problem spaces? 第一部分：在ak开始前结束的活动 构成的问题，第二部分：在ak结束后开始的 活动构成的问题，最优解由第一部分的最优 解＋{ak }＋第二部分的最优解。 3. 正确吗？如果有一个最优解，从中取出一个 活动，而后把此最优解分成两部分，问其中 的第一部分是第一个子问题的最优解吗？ 清华大学 软件学院 宋斌恒 11 最优子问题 •根据上面的分析我们构造以下子问题： •Let Sij={ak in S: f i≤sk<fk≤sj }, then Sij is the subset of S that can start after activity ai finishes and finish before activity aj starts •原问题是什么？ 清华大学 软件学院 宋斌恒 12 人工活动 •Adding two fictitious activities a0 and an+1 such that f0=0 and sn+1 = ∞, then S=S0,n+1 • 原问题S=S0,n+1！