活动选择问题 贪心选择性 口设活动S={1,2,…,n已按结束时间递增排序,即 f1f2≤…fn。每次选结束时间最小的相容活动, 可得最优解A 口证明: 设贪心最优解A也按结束时间递增排序,设其第一个 活动为k,第二个活动为j 若k=1,则成立 >若k≠1,由于A中活动相容,有f≤S1,由于1≤f, 因此,可以用活动1代替活动k 10活动选择问题 ◼ 贪心选择性  设活动S={1, 2, …, n}已按结束时间递增排序，即 f1f2….fn。每次选结束时间最小的相容活动， 可得最优解A。  证明： ➢ 设贪心最优解A 也按结束时间递增排序，设其第一个 活动为 k，第二个活动为j ➢ 若k=1，则成立 ➢ 若k1，由于 A 中活动相容，有fk  sj，由于f1  fk， 因此，可以用活动1 代替活动k 10