贪心算法的一些感悟

每一个贪心算法的背后，总有一个动态规划在默默的陪着。

                                                               ----------Endual 

    这句话的意思是贪心算法和动态规划有密切的关系，用树上的话来说，贪心算法在一些问题上比动态规划好，提高了效率，

比动态规划解决起来要好的多。

    首先我们来看一个例子：

 

 

      我们来看一个实例：

      我们有100个活动要进行，每个活动都有一个开始时间和一个结束时间。而这些活动又要共同的占有资源来进行活动，比如这些活动都只能在A教室中进行的。一个活动在进行的时候，其他的活动是不能够来进行活动的。我们要求解的是：怎样配合才能够在100个。

 

 

      我们先来看贪心算法的选择性特点：

 

 

贪心选择的性质

       第一个关键特定是贪心选择性质:一个全局最优解可以通过局部最优选择来达到。换句话说，某次选择以后，我们来解决剩余的集合的同样的问题，解出来的答案可以和我们选择出来的答案进行不修改的合并。那么，我们当考虑做什么选择的时候，我们只考虑对当前问题最佳的选择，而不考虑子问题的结果了。

贪心算法的最优子结构的问题

 

 

     我们来看最优子结构

     最优子结构的，我们把这个100活动分成两个部分，那么A部分的最后结束时间是小于B部分的最早开始时间的，这两个子问题的答案可以  经过简单的相加就可以得到我们原来问题的答案了。

 

 

贪心算法和动态规划的区别

 

以上两点是用我自己的话来说的。

   下面是算法导论的话：

     这一点是贪心算法和动态规划不一样的地方。

                      在动态规划中，每一步都要做出选择，这些选择依赖于子问题的解。因此，解动态规划问题的时候

          一般都是从子问题开始解答的，一般都是从自底向顶的方法进行解答的，从小子问题处理到大子问题。

                      在贪心算法中，我们所做的总是当前看似最佳的选择，然后再去解决选择之后所出现的子问题。贪心算法所做的当前选择可能要

                      依赖于已经做出的所有的选择，但是不会以依赖于有待于做出的选择或者子问题的解。因此，不像动态规划那样自底向上的解决子问题

                      贪心算法通常是自顶向下的做的，一个一个的做出贪心选择，不断的将给定的问题实例规约为更小的子问题中。   

 

 

贪心算法的一些性质：

 

   选择性的特定：我觉得这个贪心算法的第一点应去看这个选择性问题。我们在把原来的问题分成子问题的过程中，考虑这个问题：我们把原来的问题的数据选择一部分出去以后，剩余的数据集合中（剩余数据形成的子问题）解答出来的答案就是我们可以直接使用的。子问题的解是直接可以用，不会影响到选择出去的数据形成的子问题的解的。

 

 

 

 

     ------------当然了，问题解答有更好的文字说明，在算法导论中，或者中java版的王晓明的算法设计与分析的课本上。并且还给出来了详细的

     伪代码和思路。      

 

 

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int[] s = {0,1,3,0,5,3,5,6,8,8,2,12} ;
		int[] f = {0,4,5,6,7,8,9,10,11,12,13,14} ;
		boolean[] a = {false,false,false,false,false,false,false ,false ,false ,false,false,false} ;
		int count = greedySelector(s, f, a) ;
		System.out.println(count);
	}

	// 贪心算法的活动安排代码
	// 输入的是活动已经安排好顺序了的，从最早结束的为标志排序排序好的
	/**
	 * 
	 * @param s 开始的时间的集合，这个是按照最迟结束的时间排序好的
	 * @param f 结束的时间的集合,已经按照时间排序排序好了
	 * @param a 是否已经完成的标志
	 * @return 返回的是最大的活动数
	 */
	public static int greedySelector(int[] s, int[] f, boolean a[]) {
		
		int n = s.length - 1; //有多少活动 
		a[1] = true; //第一个活动已经完成了
		int j = 1;   //当前最近结束的活动的序号
		int count = 1; //总的活动个数已经有一个了
		for (int i = 2; i <= n; i++) { //从第二个开始，当第n个结束了
			
			if (s[i] >= f[j]) { //第i个项目的开始的时间，比第j个项目的结束时间要早要大于或者等于
				
				a[i] = true;    //那么已经完成了
				j = i;
				count++; //数量要加一个	
			}
			else {	
		       a[i] = false; //否则是没有完成的
			}
		}
		for(int i=1; i< a.length; i++) {
			
			System.out.print("  "+a[i]);
		}
		return count;
	}

}