基于活动选择问题来分析动态规划和贪心算法

今天偶然在解决活动的选择问题时遇到了一些麻烦，经过查资料和仔细分析后，总结如下，如果哪些地方有错，请指正，谢谢！

1. 动态规划算法（Dynamic Programming Algorithm）

动态规划其实和分治策略是类似的，也是将一个原问题分解为若干个规模较小的子问题，递归的求解这些子问题，然后合并子问题的解得到原问题的解。区别在于这些子问题会有重叠，一个子问题在求解后，可能会再次求解，于是我们想到将这些子问题的解存储起来，当下次再次求解这个子问题时，直接拿过来就是。其实就是说，动态规划所解决的问题是分治策略所解决问题的一个子集，只是这个子集更适合用动态规划来解决从而得到更小的运行时间。即用动态规划能解决的问题分治策略肯定能解决，只是运行时间长了。因此，分治策略一般用来解决子问题相互对立的问题，称为标准分治，而动态规划用来解决子问题重叠的问题。

动态规划一般由两种方法来实现，一种为自顶向下的备忘录方式，用递归实现，一种为自底向上的方式，用迭代实现。

2. 贪心算法（Greedy Algorithm）

贪心算法在每一步都做出最优的选择，希望这样的选择能导致全局最优解，只是寄希望，因此贪心算法并不保证得到最优解，但是它对很多问题确实可以得到最优解，而且运行时间更短。由此可见，贪心算法是带有启发性质的算法。那什么时候可以用贪心算法呢？当该问题具有贪心选择性质的时候，我们就可以用贪心算法来解决该问题。

贪心选择性质：我们可以通过做出局部最优（贪心）来构造全局最优。只要我们能够证明该问题具有贪心选择性质，就可以用贪心算法对其求解。

3. 与递归、分治的联系

分治策略用于解决原问题与子问题结构相似的问题，对于各子问题相互独立的情况，一般用递归实现；

动态规划用于解决子问题有重复求解的情况，既可以用递归实现，也可以用迭代实现；
贪心算法用于解决具有贪心选择性质的一类问题，既可以用递归实现，也可以用迭代实现，因为很多递归贪心算法都是尾递归，很容易改成迭代贪心算法；
递归是实现手段，分治策略是解决问题的思想，动态规划和贪心算法很多时候会使用记录子问题运算结果的递归实现。
4. 实例解析：基于活动选择问题来分析动态规划和贪心算法
4.1 问题描述

给定n个活动以及各个活动的开始时间和结束时间，比如：

* 活动号i： 0 1 2 3 4 5 6 7 8 9 10 11 12 ……

* 开始时间s(i)： 0 1 3 0 5 3 5 6 8 8 2 12 20……

* 结束时间f(i)： 0 4 5 6 7 8 9 10 11 12 13 14 15……

* 求13个活动中最大兼容活动的个数?

4.2 问题分析
* 使用动态规划算法思路分析

**问题一般化

首先通过前面的几个简单的例子来实际分析下，活动1的开始时间s(1)=1，结束时间f(1)=4，它与活动2是不兼容的。因为，活动1还没有结束，活动2就开始了(s(2) < f(1))。

活动2 与 活动4 是兼容的。因为，活动2的进行区间是[3,5) 而活动4的进行区间是[5,7)，所以看来，问题的最终目标是在N个活动中找出最大兼容的活动个数。

**建模

活动 i 用 a(i)来表示，开始时间用 s(i)表示，结束时间用 f(i)表示，所有活动的集合为S，定义一个合适的子问题空间，设 S(i,j) 是与 a(i) 和 a(j)兼容的活动集合，且S(i,j)={a(k), a(k) belongs to S: f(i)<=s(k) ，S=S(0,n+1)，从N个活动中找出最大兼容的活动，就转化成了求解 S(0,n+1)集合中包含的最多元素个数。

**子问题分析

假设所有的活动都按结束时间递增排序。子问题空间就是 从S(i,j)中选择最大兼容活动子集，即max{S(i,j)}（max{S(i,j)}表示与 a(i) a(j) 兼容的最大活动集合。称为为S(i,j)的解）

假设 a(k)是 S(i,j)的解包含的一个活动。S(i,j)就分解为 max{S(i,k)} + max{S(k,j)}+1，从这里可以看到，将原问题分解成了两个子问题。原问题就是：求解与活动 a(i) a(j) 兼容的最大活动个数，即max{S(i,j)}，而子问题则是：max{S(i,k)} 和 max{S(k,j)}，设A(i,j)就是S(i,j)的解。那么，A(i,j)=A(i,k) U A(k,j) U {a(k)}，A(0,n+1)就是我们所求的整个问题的最优解。

**问题转化的状态转移方程

从上面分析可以看出：原问题分解成了两个子问题，要解决原问题，一共有 j-i+1中选择，然后一 一遍历求出所有的选择。这就是动态规划的特点，先分析最优子问题，然后再做选择。

* 使用贪心算法思路分析：

所谓贪心算法，就是每次在做选择时，总是先选择具有相同特征的那个解，即“贪心”解。在这里，“贪心”的那个解则是： 结束时间最早的那个活动

具体步骤如下：

第一步：先对活动按照结束时间进行排序。因为我们总是优先选择结束时间最早的活动的嘛；

第二步：按照贪心原则选中一个活动，然后排除 所有与该活动 有冲突的活动；

第三步：继续选择下一个活动。其实，第二步与第三步合起来就是：每次都选结束时间最早的活动，但是后面选择的活动不能与前面选择的活动有冲突。

当选择了贪心解时(结束时间最小的活动)，也是将原问题划分成了两个子问题，但是其中一个子问题是空的，而我们只需要考虑另一个非空的子问题就可以了，结合题目而言就是：

假设 a(m) 是 S(i,j)中具有最早结束时间的那个活动，那按照我们的贪心选择，我们肯定会选择a(m)的嘛。选了a(m)之后，就将问题分解成了两个子问题:S(i,m) 和 S(m,j)。前面提到，活动是按结束时间排序了的，而现在a(m)又是最早结束的活动，因为，S(i,m)就是个空集，而我们只需要考虑S(m,j)。

4.3 代码实现

package dynamicProgram;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

/**
 * 基于活动选择问题来分析动态规划和贪心算法
 * 需求：给定n个活动以及他们的开始时间和结束时间，比如：
 * 活动i：                 1   2   3   4......
 * 开始时间s(i)：  1   3   0   5......
 * 结束时间f(i)：  4   5   6   7......
 * 求n个活动中最大兼容活动的个数?
 * @author 芷若初荨
 * @param  n 活动数目
 * @param  s 开始时间
 * @param  f 结束时间
 * return  最大兼容活动个数
 */
public class DPAlgorithm {
    public static void main(String[] args) {
//      定义开始时间
        int[] s = {0,1,3,0,5,3,5,6,8,8,2,12,20};
//      定义结束时间
        int[] f = {0,4,5,6,7,8,9,10,11,12,13,14,25};
//      定义活动个数
        int n;
        System.out.println("a:动态规划算法      b:贪心的递归解     c:贪心算法的非递归解");
        System.out.println("请输入解题方式：");
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        try {
            String type=br.readLine();
            //      采用动态规划方式解题
            if("a".equals(type)){
                System.out.println("请输入活动个数n：");
                n=Integer.parseInt(br.readLine());
                int result = dynamicProgramAlgorithm(s, f, n);
                System.out.println("最大兼容活动个数: " + result);
              }
//          贪心的递归解
            else if("b".equals(type)){
                System.out.println("请输入活动个数n：");
                n=Integer.parseInt(br.readLine());
                 ArrayList<Integer> acts = new ArrayList<Integer>();
                 GreedyAlgorithmRecursive(s, f, 0, n, acts);
                    for (Integer activityId : acts){
                        System.out.print("活动号为："+activityId + " ");
                    } 
            }
//          采用贪心算法的非递归解
            else if("c".equals(type)){
                System.out.println("请输入活动个数n：");
                n=Integer.parseInt(br.readLine());
                ArrayList<Integer> acts1 = new ArrayList<Integer>();
                GreedyAlgorithmNoRecursive(s, f, n, acts1);
                for (Integer activityId : acts1){
                    System.out.print("活动号为："+activityId + " ");
                }

            }
            else{
                System.out.println("您的操作有误，请重新输入！");
            }

          } catch (IOException e) {
            // TODO Auto-generated catch block
              e.printStackTrace();
              System.out.println("对不起，系统正在忙！");
          } 

    }
    //基于动态规划算法解决活动选择问题：
    /*这里的 S(i,j)一共大约有N^2个， 因为 1=j没有实际意义嘛）,每个S(i,j)一共有 j-i+1种 选择
            故时间复杂度为O(N^3)
    */
    public static int dynamicProgramAlgorithm(int[] s, int[] f, int n){
        int[][] c = new int[n + 2][n + 2];
        for(int j = 0; j <= n+1; j++)
            for(int i = n+1; i >= j; i--)
                //设S(i,j)为c[i,j]的最大兼容自己活动数
                //如果i>=j，那么S(i,j)集合为空集合，即不存在可兼容的活动
                c[i][j] = 0;
                int maxTemp = 0;
                for(int j = 1; j <= n+1; j++)
                {
                    for(int i = 0; i < j; i++)//i < j            
                        {
                        for(int k = i+1; k < j; k++)// i< k                 
                            {
                            if(s[k] >= f[i] && f[k] <= s[j])//S(i,j)不空                 
                                {
                                if(c[i][k] + c[k][j] + 1 > maxTemp)
                                    maxTemp = c[i][k] + c[k][j] + 1;
                            }
                   }
                c[i][j] = maxTemp;
                maxTemp = 0;
            }
        }
        return c[0][n+1];
    }
    //基于贪心算法解决活动选择问题(可以采用递归也可以采用非递归)
   //因为对于贪心算法而言，每次只有一种选择即贪心选择，而DP中每个问题S(i,j)中 j-i+1种选择。
   //   故时间复杂度为O(N)
    //贪心算法的递归解
    public static ArrayList<Integer> GreedyAlgorithmRecursive(int[] s,int[] f,int i,int n,ArrayList<Integer> activities){
        int m=i+1;
    //初始调用时i=0,所以a（1）是必选的
        while(m <= n && s[m] < f[i]){
            //s[m] < f[i] 意味着活动 a(m) 与 a(i)冲突了
            m++;//选择下一个活动
        }
            if(m<=n){
                activities.add(m);
                GreedyAlgorithmRecursive(s,f,m,n,activities);
            }

        return activities;      
    }
    //贪心算法的非递归解
    //所有真正的活动(不包括 活动0和 活动n+1)中,结束时间最早的那个活动一定是最大兼容活动集合中的 活动
    public static ArrayList<Integer> GreedyAlgorithmNoRecursive(int[] s,int[] f,int n,ArrayList<Integer> activities){
         int m=1;
         activities.add(m);
         for(int actId=2;actId<=n;actId++){
             if(s[actId]>=f[m]){
                 //如果actId的开始时间在m号活动之后，说明actId与m活动没有冲突
                 m=actId;//记录下当前的活动号
                 activities.add(m);//继续寻找下一个
             }
         }
        return activities;
    }

}

4.4 运行结果

动态规划算法解

贪心算法递归解

贪心算法非递归解

4.5 效率分析及算法评价

*时间复杂度：

动态规划算法的时间复杂度与问题的个数以及每个问题的选择数有关，在这段代码中，S(i,j)一共大约有N^2个， 因为 1=j没有实际意义）,每个S(i,j)一共有 j-i+1种 选择，因此时间复杂度为O(N^3)；

在贪心算法中，我们只能看到一个for循环，每个活动只会遍历一次，另外每次只有一种选择即贪心选择，而DP中每个问题S(i,j)中 j-i+1种选择。贪心算法做出一次贪心选择后，即选中某个活动后，活动个数减少1，即问题规模减少1，因此贪心算法的时间复杂度为O(N)；

*空间复杂度：

动态规划实现直接是采用数组存储，数组是大小固定的，并且同一个数组只能存放类型一样的数据（基本类型/引用类型）， 效率高，但容量固定且无法动态改变，内存占用和数组长度有关，并且当数组长度达到很大时，容易溢出；

贪心算法实现是采用集合的方式存储，集合可以存储和操作数目不固定的一组数据，集合只能存放引用类型的数据，不能存放基本数据类型，实质上集合也是采用数组来封装的，任何一个数组比集合的速度都要快。

评价：

在时间复杂度上，我们可以看出动态规划的效率明显低于贪心算法，如果对于一个固定长度的活动数目时，我们可以采用贪心算法；

在空间复杂度上，结合具体活动数目来定采用哪种方式来解决。

5.小结

*动态规划是先分析子问题，再做选择。而贪心算法贪心算法则是先做贪心选择，做完选择后，生成了子问题，然后再去求解子问题；

*动态规划每一步可能会产生多个子问题，而贪心算法贪心算法每一步只会产生一个子问题；

* 从特点上看，动态规划是自底向上解决问题，而贪心算法则是自顶向下解决问题。