贪心

最优化问题的求解往往需要通过一系列步骤，每个步骤面临许多选择。对于一些简单的问题若使用动态规划来求解有些大材小用的感觉。 贪心算法(Greedy) 便是一种更简单、更高效的算法。 # 概述 贪心算法对一个多步骤逐步求解的问题，将在每一步都选择当前最优的策略，而不去关注之前或后续的步骤。贪心算法在大部分问题上都不会取得最优解，因为它并没有测试所有的可能解，容易过早的做决定。对于有的问题只能得到一个近似最优解，但是在某些问题上它确实能够获得最优解，如求图中的最小生成树、求哈夫曼编码。一旦某问题可以用贪心来求解，那么贪心一般是最高效的解决方式。可以用贪心算法解决的题目需要满足以下性质： * 最优子结构：一个问题的最优解包含其子问题的最优解 * 贪心选择性：所求问题的整体最优解可以通过一系列局部最优的选择来到达，即通过贪心选择来达到

贪心与动态规划

在动态规划中，每一个步骤都要进行选择，这个选择通常依赖于子问题；而贪心算法并不需要考虑子问题，直接选择看起来最优的解。所以动态规划通常是递推形式，先计算较小的子问题，为较大的问题提供铺垫；在贪心算法中，我们常常自顶向下求解问题，每一次选择局部最优解，最后留下一个唯一的子问题。

贪心过程

从问题的某一初始解出发
    while (能朝给定总目标前进一步) 
        do
            选择当前最优解作为可行解的一个解元素；
    由所有解元素组合成问题的一个可行解。

0-1背包和分数背包

若有三个物体，他们的重量和价值分别为weight = [1, 2, 3]；value = [6, 10, 12]. 他们的平均价值分别为[6, 5, 4]，现在有一个可以装5重量的背包，要如何装才能使得收益最大化？
* 0-1背包：每一种物体只能选择装或者不装。 * 分数背包： 每一种物体可以划分开来装。

0-1 背包

对于0-1背包问题采用贪心策略：优先装平均收益最大的物体。最终的背包将会装下物体1和物体2而不能装下物体3，背包占用3剩余2，总价值为16.但是显而易见的装物体2和物体3才是最优策略，此时背包刚好被占满，总价值为22.所以贪心在0-1背包并不适用。

分数背包

分数背包可以适用贪心获取最优解。证明也是很简单的：背包的容量有限，要是价值最大，其中物体的平均价值就得最大，所以优先装平均价值最大的物体，最终的总价值也将会最高。最终背包装了物体1、物体2和\(\frac{2}{3}\)的物体3，最终价值为24.

贪心适用性证明

贪心策略很容易理解，但一个问题是否适用于贪心算法的证明是最难的。

归纳法

数学归纳法的一般步骤为： 1. 证明\(n=1\)时命题成立 2. 假设\(n=k\)时命题成立 3. 证明\(n=k+1\)时命题成立

交换论证法

• 分析一般最优解与贪心法的解的区别，然后定义一种转换规则，使得从任意一个最优解出发，经过不断对解的某些成分的排列次序进行交换或者用其他元素替换，将这个解最终能够转变成贪心法的解。
• 证明在上述转换中解得优化函数值不会变坏。
• 证明上述转换在有限步结束。