活动选择问题（动态规划和贪心算法）

有一个由n个活动组成的集合S = {a1, ..., an}

    1. 这些活动使用同一个资源，而这个资源在某一时刻只供一个活动使用

    2. 每个活动都有一个开始和结束时间si/fi；如果被选中，则任务ai发生在半开时间区间[si, fi)

    3. 如果两个活动ai和aj不重叠，则称两个活动兼容

     活动选择问题，希望选出一个最大兼容活动集

    假设活动已经按结束时间递增排好序

最优子结构

    Sij表示在ai结束之后，aj开始之前结束之前的活动集合；Aij表示Sij的一个最大兼容活动集

    假设Aij包含ak， 则得到两个子问题，寻找Sik以及Skj的最大兼容活动集

    用c[i, j]表示集合Sij的最优解的大小，则可得递归式：c[i, j] = c[i, k] + c[k, j] + 1

    从而实际上

    c[i, j] = 0    if Sij = 空集

                max{c[i, k] + c[k, j] +1}    ak属于Sij

活动选择问题的另一个性质，使得无须求解所有子问题就可以选择出一个活动加入到最优解；选择的标准为，选出活动后剩下的资源应能被尽量多的其他任务所用 【选择最早结束的活动】

定理可以证明：任意非空子问题Sk，am是Sk中结束时间最早的活动，则am在Sk的某个最大兼容活动子集中【 假设一个最大兼容活动子集Ak，用am替代Ak中最早结束的活动得到Ak'，依然是最大兼容活动子集】

——>贪心算法，自顶向下的设计，做出一个选择，然后求解剩下的那个子问题，而不像动态规划自底向上地求解很多子问题，然后再做出选择

假设已经按照活动结束时间排好序

递归贪心算法：

RECURSIVE-ACTIVITY-SELECTOR(s, f, k, n)             // s表示活动的开始时间数组；f表示结束时间数组；k表示上一个选中的活动，初始为0【引入a[0]，其结束时间为0】；n为问题规模

    m = k + 1

    while(m<=n && s[m] < f[k])         //活动必须在活动集合中；且其开始时间必须比上一个活动的结束时间晚

        m = m + 1

    if m<=n

        return a[m] 并上  RECURSIVE-ACTIVITY-SELECTOR(s, f, m, n)

    else

        return 空集

迭代贪心算法：（通常“尾递归”的算法都可以很直接的转化为迭代形式）

GREEDY-ACTIVITY-SELECTOR(s, f)

    n = s.length

    A = {a1}

    k = 1

    for m = 2 to n

        if(s[m] >= f[k])

            A = A 并上 {am}

            k = m

    return A