贪心算法解活动选择问题的正确性 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 a=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=Ak-aam be Ak but substitutingfor.The activities in A are disjoint,which follows because the activities in Ak are disjoint,aj is the first activity in Ak to finish,and ffi. Since =Ak we conclude that A is a maximum-size subset of mutually compatible activities of Sk,and it includes贪心算法解活动选择问题的正确性