清华大学出版社 TSINGHUA UNIVERSITY PRESS 4.1活动安排问题 若被检查的活动的开始时间Si小于最近选择的活动j 的结束时间f,则不选择活动i,否则选择活动i加入集 合A中。 贪心算法并不总能求得问题的整体最优解。但对 于活动安排问题,贪心算法 greedy Selecto却总能求 得的整体最优解,即它最终所确定的相容活动集合A的 规模最大。这个结论可以用数学归纳法证明。10 4.1 活动安排问题 若被检查的活动i的开始时间Si小于最近选择的活动j 的结束时间fi，则不选择活动i，否则选择活动i加入集 合A中。 贪心算法并不总能求得问题的整体最优解。但对 于活动安排问题，贪心算法greedySelector却总能求 得的整体最优解，即它最终所确定的相容活动集合A的 规模最大。这个结论可以用数学归纳法证明