贪心法适用范围 贪心选择性质一正确性 ■所求问题的最优解,可以通过一系列的局部 最优解的选择,即贪心选择得到 ■满足贪心选择得到最优解,否则为近似解 需要证明,一般采用数学归纳法 ■对选择步骤归纳 ■对问题规模归纳
贪心法适用范围 贪心选择性质 —正确性 所求问题的最优解，可以通过一系列的局部 最优解的选择，即贪心选择得到 满足贪心选择得到最优解，否则为近似解 需要证明，一般采用数学归纳法 对选择步骤归纳 对问题规模归纳
贪心选择性质证明(归纳基 础) 设S={12r…}是活动集,活动按截止时间递 增顺序排序 k=1,证明存在最优解包含活动1 任取最优解AA中的活动按照截止时间递增 的顺序排列.如果A的第一个活动为,子1, 令=G4份){1}由于八≤历也是最优 解,且含有1
贪心选择性质证明（归纳基 础） 设 S={1,2, … , n}是活动集，活动按截止时间递 增顺序排序 . k=1, 证明存在最优解包含活动1. 任取最优解 A, A中的活动按照截止时间递增 的顺序排列. 如果 A的第一个活动为j， j≠1, 令 A’= ( A− {j}) ∪{1}, 由于 f1 ≤fj, A’也是最优 解，且含有1