贪心算法的一些感悟
每一个贪心算法的背后，总有一个动态规划在默默的陪着。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?----------Endual?
? ? 这句话的意思是贪心算法和动态规划有密切的关系，用树上的话来说，贪心算法在一些问题上比动态规划好，提高了效率，
比动态规划解决起来要好的多。
? ? 首先我们来看一个例子：
?
?
? ? ? 我们来看一个实例：
? ? ? 我们有100个活动要进行，每个活动都有一个开始时间和一个结束时间。而这些活动又要共同的占有资源来进行活动，比如这些活动都只能在A教室中进行的。一个活动在进行的时候，其他的活动是不能够来进行活动的。我们要求解的是：怎样配合才能够在100个。
?
?
? ? ? 我们先来看贪心算法的选择性特点：
?
?
贪心选择的性质
? ? ? ?第一个关键特定是贪心选择性质:一个全局最优解可以通过局部最优选择来达到。换句话说，某次选择以后，我们来解决剩余的集合的同样的问题，解出来的答案可以和我们选择出来的答案进行不修改的合并。那么，我们当考虑做什么选择的时候，我们只考虑对当前问题最佳的选择，而不考虑子问题的结果了。
贪心算法的最优子结构的问题
?
?
? ? ?我们来看最优子结构
?? ? 最优子结构的，我们把这个100活动分成两个部分，那么A部分的最后结束时间是小于B部分的最早开始时间的，这两个子问题的答案可以? 经过简单的相加就可以得到我们原来问题的答案了。
?
?
贪心算法和动态规划的区别
?
以上两点是用我自己的话来说的。
? ?下面是算法导论的话：
? ? ?这一点是贪心算法和动态规划不一样的地方。
? ? ? ? ? ? ? ? ? ? ? 在动态规划中，每一步都要做出选择，这些选择依赖于子问题的解。因此，解动态规划问题的时候
? ? ? ? ? 一般都是从子问题开始解答的，一般都是从自底向顶的方法进行解答的，从小子问题处理到大子问题。
? ? ? ? ? ? ? ? ? ? ? 在贪心算法中，我们所做的总是当前看似最佳的选择，然后再去解决选择之后所出现的子问题。贪心算法所做的当前选择可能要
? ? ? ? ? ? ? ? ? ? ? 依赖于已经做出的所有的选择，但是不会以依赖于有待于做出的选择或者子问题的解。因此，不像动态规划那样自底向上的解决子问题
? ? ? ? ? ? ? ? ? ? ? 贪心算法通常是自顶向下的做的，一个一个的做出贪心选择，不断的将给定的问题实例规约为更小的子问题中。 ??
?
?
贪心算法的一些性质：
?
? ?选择性的特定：我觉得这个贪心算法的第一点应去看这个选择性问题。我们在把原来的问题分成子问题的过程中，考虑这个问题：我们把原来的问题的数据选择一部分出去以后，剩余的数据集合中（剩余数据形成的子问题）解答出来的答案就是我们可以直接使用的。子问题的解是直接可以用，不会影响到选择出去的数据形成的子问题的解的。
?
?
?
?
? ? ?------------当然了，问题解答有更好的文字说明，在算法导论中，或者中java版的王晓明的算法设计与分析的课本上。并且还给出来了详细的
? ? ?伪代码和思路。 ? ? ?
?
?
??
?
