贪心算法的原理与设计
贪心算法的设计步骤
1、将最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题要求解。
这个问题可以引用前面得到的活动选择问题进行说明 ，如在活动选择问题中，设Aij 代表的是活动ai?
结束后开始，且在aj结束之前进的一个子问题，于是
Aij=Aik+ak+Akj
于我们将区间【i,j】活动的安排就变成了两个子区间【i,k】和【k,j】的优化问题，这问题进行了变化。
但是如果我们如果采用贪心策略，先对活动的结束时间进行排序，也就是每次都优先选择结束时间早
的问题，这样，我们就将问题解化了，首先，我们不需要用区间来表示了，我们只要选择活动就行了
，其次，我们只有一种选择了，只剩下一个子问题需要我们进行求解，也就是在剩下的活动中，再
次选择结束时间最早且起始时间又符合我们要求的子问题。这样选择便只有一个了。
2、证明贪心选择后，问题总是存在最优解，即贪心总是安全的。
3、证明贪心选择后，剩余子问题满足性质：其最优子解与贪心选择组合后便得了原问题的最优解。
贪心算法可能依览之前做出的选择，如活动安排问题，但是与后面做的选择无关，也就是不依缆
之后的选择。
3、贪心算法的原理与设计
原文：http://www.cnblogs.com/yml435/p/4655576.html
