贪心算法解活动选择问题的正确性 Theorem 16.1 Consider any nonempty subproblem Sk,and let am be an activity in Sk with the earliest finish time.Then a is included in some maximum-size subset of mutually compatible activities of Sk. Proof Let Ak be a maximum-size subset of mutually compatible activities in Sk, and let a;be the activity in Ak with the earliest finish time.If aj=am,we are done,since we have shown that am is in some maximum-size subset of mutually compatible activities of Sk.If ajam,let the set A=Akaam)be Ak but substituting a for a.The activities in A are disjoint,which follows because the activities in Ak are disjoint,aj is the first activity in Ak to finish,andffi. Since A=Ak,we conclude that A is a maximum-size subset of mutually compatible activities of Sk,and it includes a贪心算法解活动选择问题的正确性