对于一些最优解问题，每一步都做当前的最优选择，最后得到的选择结果就是最终问题的最优解，这样的问题就适用贪心算法。贪心算法在每一步做出局部的最优选择，最后得到整个问题的最优解。显然，实际问题中存在大量问题并不是每一步最优就能最终最优的，如01背包问题，因此贪心算法解决问题简化了解决方案，但是得到的最终结果的可信度不如动态规划算法或者分治算法高，往往考虑不够全面。问题能否使用贪心算法解决要根据问题实际分析。
二.活动选择问题
有n个需要在同一天使用同一个教室的活动a1,a2,…,an，教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行（最大兼容活动子集）。例如下图所示的活动集合S，其中各项活动按照结束时间单调递增排序。
{a3,a9,a11}是一个兼容的活动子集，但它不是最大子集，因为子集{a1,a4,a8,a11}更大，实际上它是我们这个问题的最大兼容子集，但它不是唯一的一个{a2，a4，a9，a11}
1.动态规划算法
static void Main(string[] args) { //添加两个活动，一个从0点到0点，一个从24点到24点 //记录活动start时间的数组 int[] s = { 0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12, 24 }; //记录活动end时间的数组 int[] e = { 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 24 }; //记录所有方案的二维数组 //数组的行数和列数对应了活动方案的编号，如result[3,7]代表了第3个到第7个活动的活动最大兼容子集 List<int>[,] result = new List<int>[13, 13]; //为二维数组赋初值，集合中的数字代表哪些活动组合成最大兼容子集 for (int m = 0; m < 13; m++) { for (int n = 0; n < 13; n++) { result[m, n] = new List<int>(); } } //双重循环 //依次遍历存储所有活动的最大兼容子集，j是最后一个活动编号，i是第一个活动编号 for (int j = 0; j < 13; j++) { for (int i = 0; i < j - 1; i++) { //int集合sij用于存储计算出的第i到第j个活动的最大兼容子集 List<int> sij = new List<int>(); //循环遍历每一个活动，number是当前指向的活动编号 for (int number = 1; number < s.Length - 1; number++) { //如果当前遍历到的活动的时间在最后一个活动j的开始时间和第一个活动i的结束时间之间，这个活动就能插入两个活动之间进行 if (s[number] >= e[i] && e[number] <= s[j]) { sij.Add(number); } } //如果有活动插入到了两个活动之间 if (sij.Count > 0) { //保存最大兼容子集的活动的数量 int maxCount = 0; //保存最大兼容子集 List<int> tempList = new List<int>(); //循环遍历插入的活动 foreach (int number in sij) { //计算最大兼容子集的活动的数量 int count = result[i, number].Count + result[number, j].Count + 1; //更新最大兼容子集的活动数量 //可能有多个活动可以插入两个活动之间，因此需要判断哪一个活动插入后是从i活动到j活动的最大兼容子集 //将最大兼容子集的活动编号保存起来 if (maxCount < count) { maxCount = count; tempList = result[i, number].Union<int>(result[number, j]).ToList<int>(); tempList.Add(number); } } //更新计算出的i活动到j活动的最大兼容子集 result[i, j] = tempList; } } } //结果取出第0个活动到第12个活动的最大兼容子集即可 List<int> a = result[0, 12]; foreach (int item in a) { Console.Write(item + " "); } Console.ReadKey(); }