1、前言
求解最优化问题的算法通常会经历一系列步骤，在每个步骤都会面临多种选择，而许多最优化问题并不需要计算每个选择，它的选择非常明确。
贪心算法就是这样的算法，它在每一步中都做出当时看起来最佳的选择，它总是做出局部最优选择从而实现最优解
2、贪心算法原理
贪心算法的步骤：
- 确定总是的最优子结构
- 设计一个递归算法
- 证明如果我们做出一个贪心选择，则只剩下一个子总是
- 证明贪心选择总是安全的
- 设计一个递归算法实现贪心策略
- 将递归算法转换为迭代算法
什么时候才能使用贪心算法的呢？书中给出了贪心算法的两个性质，只有最优化问题满足这些性质，就可采用贪心算法解决问题。
（1）贪心选择性质：一个全局最优解可以通过最优解（贪心）选择来达到。即：当考虑做选择时，只考虑对当前问题最佳的选择而不考虑子问题的结果。
（2）最优子结构：问题的一个最优解包含了其子问题的最优解。
贪心算法一般来说都能用动态规划解决，因为动态规划需要的条件，贪心算法都满足，而贪心算法像是简化版的动态规划，它不需要计算每个选择。贪心算法只需要选择一个当下最优选择即可。
3、活动选择问题
假定由n个活动组成的集合S= {a1，a2，···，an }，这些活动使用同一个资源。每个活动ai都有一个开始时间si和结束时间fi，且 0≤si<fi<∞ 。被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，则称ai和aj两个活动是兼容的。
该问题就是要找出一个由互相兼容的活动组成的最大子集。例如下图所示的活动集合S，其中各项活动按照结束时间单调递增排序。
根据上图可知，最大子集为1、4、8、11。
4、动态规划解题
最大活动子集问题是否满足最优子结构呢？仔细思考发现此问题类似于钢条切割问题，使用复制剪切法，将最优解分为两个规模相当的子问题，那么子问题必然也是最优解。
具有最优子结构，那么它的状态方程式是什么呢？
定义子问题解空间Sij是S的子集，其中每个活动都是在ai结束之后开始，且在aj开始之前结束。当 i>=j 时，Sij为空集。
设c[i][j]为Sij中最大兼容子集中的活动数目，当Sij为空集时，c[i][j]=0；当Sij非空时，若ak在Sij的最大兼容子集中被使用，则则问题Sik和Skj的最大兼容子集也被使用，故可得到c[i][j] = c[i][k]+c[k][j]+1。
由此可知状态方程式为：
/**
* 动态规划计算最大活动数。
* 此问题满足最优子问题条件，而且可推导公式为：
* max = Math.max(max, c[i][k] + c[k][j] + 1);
* 类似钢条切割，一定是中间某点分割，两边都是最优选
*/
public static int dpSelect(){
int[] st = {1,3,0,5,3,5,6,8,8,2,12};
int[] ft = {4,5,6,7,8,9,10,11,12,13,14};
int length = st.length;
int[][] c = new int[length][length];
int[][] ret = new int[length][length];
for (int i = 0; i < length; i++) {
for (int j = 1; j < length; j++) {
if (i == j) {
c[i][j] = 0;
}else {
int max = 0;
for (int k = i+1; k < j; k++) {
if (st[k] >= ft[i] && ft[k] <= st[j]) {
max = Math.max(max, c[i][k] + c[k][j] + 1);
ret[i][j] = k;
}
}
/*
* max等于0，即没有合适的k。
* 如果集合的首位和末位时间合适，所以会有两个活动
* 如果集合的首位和末位时间不合适，所以会有一个活动
*/
if (max == 0) {
if (st[j] >= ft[i]) {
max += 2;
}else {
max += 1;
}
}
c[i][j] = max;
}
}
}
System.out.println(c[0][10]);
System.out.println("----------");
printResult(st, ft, 0, 10, ret);
return c[0][length-1];
}
printResult方法，根据ret数组中的值，计算一共选择了哪些活动。
public static void printResult(int[] st, int[] ft, int i, int j, int[][] ret){
int r = ret[i][j];
if (r > 0) {
System.out.println(r);
}
while (r > 0 && r < st.length && (r=ret[i][r]) > 0) {
System.out.println(r);
}
if (st[j] >= ft[i]) {
System.out.println(i);
System.out.println(j);
}else {
System.out.println(i);
}
}
5、贪心算法
贪心算法是动态规划的简化版本。
此问题使用贪心算法非常简单，因为活动结束时间已经按照从小到大顺序排列了，为了实现最大子集的目标，所以第1个活动一定要入选，因为第1个活动最早结束，能够给出最多的时间让其它活动入选。
接下来遍历每一个活动，只要新活动的开始时间大于或等于已经入选的活动，则此活动也可以入选。因为结束时间从小到大排列的原因，新入选的活动一定是最优的。
代码如下：
/**
* 贪心算法计算最大活动数
*/
public static void greedSelect(){
int[] st = {1,3,0,5,3,5,6,8,8,2,12};
int[] ft = {4,5,6,7,8,9,10,11,12,13,14};
int length = st.length;
int current = 0;
System.out.println("0 is selected");
for (int i = 1; i < length; i++) {
//因为活动结束时间已经按从小到大顺序排列，那么只要活动开始时间大于current结束时间
//那么此活动一定会是最优的。有可能其它活动开始时间也满足要求，但他们的结束时间一定比i大。
if (st[i] >= ft[current]) {
current = i;
System.out.println(current + " is selected");
}
}
}
ps：所有代码均已上传至本人的github，欢迎访问
