贪心算法

1.性质

贪心算法通过一系列的选择来得到问题的解。它所做的每一个选择都是当前状态下局部的最好选择，即贪心选择。

贪心选择的一般特征：贪心选择性质和最优子结构性质。

在动态规划算法中，每步所作的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能作出选择。

而在贪心算法中，仅在当前状态下作出最好选择，即局部最优选择。然后再去解作出这个选择后产生的相应的子问题。

贪心算法所作的贪心选择可以依赖于以往所作过的选择，但决不依赖于将来所作的选择，也不依赖于子问题的解。正

是由于这种差别，动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行,以迭代

的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为一个规模更小的子问题。

对于一个具体问题，要确定它是否具有贪心选择性质，我们必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。

通常可以用我们在证明活动安排问题的贪心选择性质时所采用的方法来证明。首先考察问题的一个整体最优解，并证明可修改

这个最优解，使其以贪心选择开始。而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证

明，通过每一步作贪心选择，最终可得到问题的一个整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题

的关键在于利用该问题的最优子结构性质。

2.最优子结构

  当一个问题的最优解包含着它的子问题的最优解时，称此问题具有最优子结构性质。问题所具有的这个性质是该问题可用动态

规划算法或贪心算法求解的一个关键特征。在活动安排问题中，其最优子结构性质表现为：若a是对于正的活动安排问题包含活动

1的一个最优解,则相容活动集合a’=a—{1}是对于e’={i∈e:s_i≥f₁}的活动安排问题的一个最优解。

3.贪心算法与动态规划算法的区别

贪心算法和动态规划算法都要求问题具有最优子结构性质，这是两类算法的一个共同点。大多数时候，能用贪心算法求解的问题，都可以用动

态规划算法求解。但是能用动态规划求解的，不一定能用贪心算法进行求解。

【一】动态规划：

       依赖：依赖于有待做出的最优选择

       实质：就是分治思想和解决冗余。

       自底向上（每一步，根据策略得到一个更小规模的问题。最后解决最小规模的问题。得到整个问题最优解）

        特征：动态规划算法的每一步决策给出的不是唯一结果，而是一组中间结果，而且这些结果在以后各步可能得到多次引用，只是每走一步使问题的规模逐步缩小

　　，最终得到问题的一个结果。

          缺点：空间需求大。

【二】贪心算法：

       依赖：依赖于当前已经做出的所有选择。

       自顶向下（就是每一步，根据策略得到一个当前最优解。传递到下一步，从而保证每一步都是选择当前最优的。最后得到结果）

4.使用范围

贪心算法并不能总求得问题的整体最优解。但对于某些问题，却总能求得整体最优解，这要看问题时什么了。只要能满足贪心算法的两个性质：

贪心选择性质和最优子结构性质，贪心算法就可以出色地求出问题的整体最优解。即使某些问题，贪心算法不能求得整体的最优解，贪心算法

也能求出大概的整体最优解。如果你的要求不是太高，贪心算法是一个很好的选择。最优子结构性质是比较容易看出来的，但是贪心选择性质

就没那么容易了，这个时候需要证明。证明往往使用数学归纳法。