nS={12…n}为n项活动的集合 s和分别表示活动开始和结束时间(1≤i≤n) 活动和活动相容当且仅当s≥f或S12f i1234567891011 s1031355688212 f6548791011121314 求出两两相容的最大活动集合
◼ S={1,2,…,n}为n项活动的集合 ◼ si和fi分别表示活动i开始和结束时间(1 ≤ i ≤ n) ◼ 活动i和活动j相容当且仅当si ≥ fj或sj ≥ fi ◼ 求出两两相容的最大活动集合 s i i f i 1 2 3 4 5 6 7 8 9 10 11 si 0 3 1 3 5 5 6 8 8 2 12 fi 6 5 4 8 7 9 10 11 12 13 14
活动选择问题 ■按照结束时间f排序 1234567891011 s;130535688212 41567891011121314 两两相容的最大活动集合为 A={14811},原来未排序的{358 11
活动选择问题 ◼ 按照结束时间fi 排序 ◼ 两两相容的最大活动集合为 ◼ A = {1, 4, 8, 11}，原来未排序的 {3, 5, 8, 11} i 1 2 3 4 5 6 7 8 9 10 11 si 1 3 0 5 3 5 6 8 8 2 12 fi 4 5 6 7 8 9 10 11 12 13 14
活动选择问题 算法 Greedy select 1.//engthS 2.A-{1} 3.产1; 4.for产-2to 567 do if si then a←AU{Y a8. return A
活动选择问题 算法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
贪心法定义 a greedy algorithm always makes the choice that looks best at the moment. That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution. 《算法导论》 贪心法在每一步都做出一个局部最优的 选择,以期在总体上仍然达到最优
贪心法定义 ◼ A greedy algorithm always makes the choice that looks best at the moment. That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution. --《算法导论》 ◼ 贪心法在每一步都做出一个局部最优的 选择，以期在总体上仍然达到最优
最优选择问题 最优选择问题 N个输入 解为这N个输入的某个子集(或其他变体) 约束条件→可行解 目标函数,用于评判可行解的优劣→最优解 ■求解方法:根据约束条件和目标函数的数学模型的特 性或求解问题方法的不同进而细分为 (非)线性规划、整数规划 动态规划 回溯法 种更直接的求解方法 贪心算法
最优选择问题 ◼ 最优选择问题 ◼ N个输入 ◼ 解为这N个输入的某个子集（或其他变体） ◼ 约束条件→可行解 ◼ 目标函数，用于评判可行解的优劣→最优解 ◼ 求解方法：根据约束条件和目标函数的数学模型的特 性或求解问题方法的不同进而细分为 ◼ (非)线性规划、整数规划 ◼ 动态规划 ◼ 回溯法 ◼ 一种更直接的求解方法 ◼ 贪心算法