贪心算法思路详解

一、贪心算法是什么？

贪心算法与动态规划算法一样是用于求解最优化类问题的算法，其本质上是基于动态规划算法的改进算法，其所求解的问题是动态规划算法的一个子集。

我们知道，动态规划在求解时，会考虑子问题分解的所有可能性，而贪心算法则只会考虑其中的部分情况，这个减少的数量相当可观。但也正因为如此，贪心算法所求的结果不一定为问题的最优解，而是次优解。

对于动态规划，每个子问题，需要从多个选择中选出其收益最大（正向收益）的那个或最小的那个（负向收益），而对于贪心算法来说，选择是唯一确定的（总是选择局部最优的那个），且选择只会产生一个子问题。

如果把贪心算法的调用图画出来，会发现它是一个类似链表的线性结构，而非动态规划那样的树结构，由此也可推测贪心算法的复杂度在O（n）量级。

由于每次选择都是唯一确定的，因此贪心算法通常直接返回问题的解决方案，而非像动态规划那样，需要在计算过程中记录信息再通过这些信息进行推导。

贪心算法与动态规划的另一个不同之处在于贪心通常都是自上而下的，而动态规划通常都是自下而上的。这里的自上而下并非指递归实现，而是说解决问题的方向是从大到小，即使动态规划的自上而下带备忘的递归实现版本，形式上看是从大到小的解决问题，但实际计算时，依然需要先计算出较小问题的解。

二、贪心算法原理

一个动态规划的问题何时可以转化为贪心算法问题，我总结的规律如下：

当发现动态规划中的选择存在某种规律，使得我们可以通过这种规律直接得到该问题下的一个最优选择时便可以考虑贪心算法。

因为动态规划的一个子问题的最佳选择依赖于其子问题的计算，再说的直白点，动态规划的选择依赖于将来待解未解的子问题，而贪心算法则恰恰相反，它依赖其历史决策而非将来。

但这也并非绝对，只是说此问题有可能适用于贪心算法，到底能不能用需要加以证明，而非主观臆测。

设计贪心算法的一般步骤如下：

注意第二步与第三步的区别。第二步是在证明一个子问题的局部最优解总是存在于全局问题的一个最优解中，或者说是在证明我们所作的选择在当时来看确实是最优的。这两种说法其实是等价的，因为对于子问题S（k-1）中的一个选择a_k-1如果处于原问题S（k）的一个最优解中，那么对于子问题S（k-1）来说选择它也是没有任何问题的，也就是说它就是S（k-1）的局部最优解，所以两者的证明方式是一样的。而第三步是在证明最优子结构的正确性，即子问题本身的解也是其最优解，只有这样由以证明存在于原问题最优解中的一个选择+此选择所产生的子问题的最优解才能构成原问题的一个最优解。

例如对于活动选择问题的贪心算法的特征刻画最终得到的公式是 S（k）+a_k；其中S（k）是一个选择活动k后剩余集合构成的子问题， 第二步是在证明这个贪心选择确实在原问题的最优解中，即证明公式中a_k部分。而第三步是在证明，活动k与子问题S（k）的解构成原问题的一个最优解，即证明S（k）+a_k是原问题一个最优解，即证明S（k）得到的是其子问题本身的最优解。

那么如何证明一个贪心算法是否能够求解一个最优化问题？并没有适合所有情况的方法，但贪心选择性质和最优子结构是两个关键要素。如果我们能够证明问题具有这些性质，就向贪心算法迈出了重要一步。

贪心选择性质：我们可以通过做出局部最优(贪心)选择来构造全局最优解。换句话说，当进行选择时，我们直接做出在当前问题中看来最优的选择，而不必考虑子问题的解。

对于动态规划，它的每个选择都是实际计算只后得到的结果，无需加以证明，而对于贪心选择是我们主观上的意想，为了保证总体结果正确必须对其证明

证明贪心选择性质，即它存在于原问题最优解中通常使用替换法

为了进一步优化算法性能，通常会对输入数据进行预处理，或是采用特殊数据结构（通常是优先队列）存储，如在A*算法中会使用优先队列优化开放列表原素的获取。

这么做是为了减少对众多选择进行比较从而选出最优的那个选择所造成的开销。

既然我们可以直接判断选择的优劣，那必然存在一个评估方法，对选择进行评估，得到每个选择的分值或权重。

而对于最优子结构，我在讲解动态规划时，已经详细对其进行了介绍，这里不再说明，其证明方法是使用一种叫剪切-复制的方法。

三、再谈背包问题

在上篇讲解动态规划时，我展示了0-1背包问题的实现，那么考虑可否使用贪心算法实现0-1背包问题？为什么0-1背包问题是动态规划的经典问题，而非贪心算法的经典问题？

为了说明动态规划与贪心算法的差异，我们来研究一下0-1背包问题的变种——分数背包问题，它与0-1背包问题的区别如下所示：

两个背包问题都具有最优子结构性质

为了说明贪心算法对0-1背包问题无效，下面给出一个实例展示两者差异：

可见，看似单位价值最高的物品，实际却不在最终的选择方案中，造成这个问题的本质是我们无法证明0-1背包问题的贪心选择性质，在0-1背包问题中我们不仅要考虑物品单位价值对最终价值的影响还要考虑背包容量对最终价值的影响，最优选择方案实质上应该使得背包的有效单位价值最大化，而非物品的单位价值。选择商品1造成的空间浪费实际拉低了背包总体有效单位价值，带来的影响抵消了物品单位价值的影响。

四、活动选择问题

下面给出一个使用贪心算法解决问题的实际案例，并且为了表现出动态规划与贪心算法的关联性，我会展示如何从动态规划的思维模式过渡到贪心算法的思维模式。

我以贪心算法的经典问题活动选择问题为例，这个问题的描述大致如下：

首先，直观的感受上，这是一个动态规划问题，先尝试使用动态规划的思路求解。整体思路如下所示：

得到动态规划的递推公式，观察公式会发现，对于每种选择我们都需要求解出所有选择的子问题才能得出结论，而实际上我们发现存在某种规律使得我们可以直接确定这个选择而无需实际求解子问题。

我们主观的感觉，取活动S_ij中第一个结束的活动会是此问题的最优选择。因为活动结束越早，就越能留下更多的资源（时间）分配给其他的活动。

如果每次都这样取，那么实际上上述公式中c[i,k]变成了一个空集，子问题只剩下一个，且选择唯一，也就说公式实际变成了c[i,j]=c[k,j]+1这样的形式，其中k是c[i,j]范围内第一个结束的活动。

既然如此，那我们实际可以考虑优化最优子结构，我们只考虑后半段子问题，新的特征方程为S（k）+a_k，其中S（k）表示选择活动a_k后所产生的子问题

得到新的方程，别忘了我们还需要对其加以证明，每次选择第一个结束的活动只是我们主观臆测，那么究竟这是不是一个最优选择？有没有可能我k取的是中间某个活动，分割出的子问题比上述取法还要更优？

现在的问题就是我们需要证明每次取第一个确实是此问题下的最优选择，别忘了我之前说过，证明一个选择是局部最优选择与证明该选择在原问题的一个最优解中其实是等价的。

它们的证明过程如下所示：

之前我们也证明了此问题的最优子结构性质。说明此问题确实可以使用贪心算法求解，接下来就是设计代码实现了，到此时思路已经比较清晰了。我们假设输入以按照其选择评估指标（对于此问题就是结束时间）进行了预处理，并且为了方便算法进行初始化，我们加入一个哨兵活动（a₀，开始结束时间都为0），下面给出活动选择问题的递归与循环版本的两种代码实现：

/// <summary>
/// 活动选择问题递归实现
/// </summary>
/// <param name="s">开始时间</param>
/// <param name="f">结束时间</param>
/// <param name="k">上一个选择的活动序号</param>
/// <param name="n">活动数量</param>
/// <param name="plan">选择方案</param>
public static void GreedyRecursive(int[] s, int[] f,int k,int n,Stack<int> plan)
{
    int m = k + 1;
    while (m <= n && s[m] < f[k])
    {
        m++;
    }
    if (m<=n)
    {
        plan.Push(m);
        GreedyRecursive(s,f,m,n,plan);
    }
}

循环实现版本如下：

/// <summary>
/// 活动选择问题迭代版本
/// </summary>
/// <param name="s"></param>
/// <param name="f"></param>
/// <param name="n"></param>
public static Stack<int> GreedyIteration(int[] s, int[] f, int n)
{
    var plan = new Stack<int>();
    plan.Push(1);

    int k = 1;
    for (int i=2; i<s.Length; i++)
    {
        if (s[i] >= f[k])
        {
            plan.Push(i);
            k = i;
        }
    }
    return plan;
}

五、拟阵理论

该理论描述了很多贪心方法生成最优解的情形，它涉及一种称为“拟阵”的组合结构。虽然这种理论不能涵盖贪心方法适用的所有情况，但它确实覆盖了很多有实际意义的情况。

拟阵的定义如下：

定义比较晦涩难懂，通俗的解释，就是说对一个给定的集合，取它的满足某种性质I（独立性）的所有子集，如果存在一个集合s1是这些子集种某个子集s2的子集，那么s1同样满足性质I，这就是遗传性。而对于这些子集中的某两个子集A和B，如果A的元素比B的元素要少，那么从B中取一个A中没有的元素放到A中，新的A集合依然满足性质I，这就是交换性。

这个独立性对于不同的问题的问题有不同的解释，例如对于活动选择问题，我们要求解的是互相兼容的红动的集合，那么互相兼容这个性质就是此问题的独立性，再比如对于图来说，不存在环路的所有边集构成的集合就是它的独立性。

该理论中的一些概念：

• 扩展：如上述从B中取一个元素到A，这个元素就是A的扩展
• 独立集：满足性质I的所有S的子集称为S的独立子集
• 最大独立子集：S的所有独立子集中最大的独立子集，即不可再被扩展的独立子集
• 加权拟阵：如果集合S中每个元素都有一个加权函数w，为每个元素产生一个非负的权值，把这样的拟阵叫做加权拟阵
• 最优子集：S的所有独立子集中，所有元素权值总和最大的那个独立子集

可以证明加权拟阵的最优子集一定是其最大独立子集。

拟阵问题的贪心选择性质、最优子结构的证明较为复杂，我就不再展示，我们只需知道，任何可以形式化为拟阵的最优解问题，都可以使用贪心算法求得其最优解。

《算法导论》一书中给出了求解此类问题的通用算法框架：

其中唯一需要我们自定义的部分，也就是独立性的判断部分

使用拟阵理论求解问题的关键在于如何定义独立性，以及如何判断一个集合是否是独立的，以及证明该问题确实可形式化为拟阵问题，这需要证明问题满足拟阵的性质，其中难点是证明拟阵的交换性

我们所熟知的图的最小生成树算法其实就利用了拟阵理论：

关于其拟阵性质的证明较为复杂，不再展示。

下面我尝试利用此理论，解决活动选择问题，证明其可形式化为拟阵问题。我们最终要求解的是互相兼容的活动的最大集合，那么就将独立性定义为集合中的活动互相兼容，遗传性显而易见很容易证明，但是在证明交换性时我们发现此问题并不满足此性质，因为可以找出不满足的反例。所以得出结论活动选择问题不是一个拟阵问题。

总结

本文分析了动态规划与贪心算法之间的关联与差异，以及使用实际案例，详细阐述了如何从动态规划思维转变到贪心算法思维，相信这篇文章能够给读者很大启发，关于拟阵部分的理论了解即可，重点是掌握贪心算法的思维模式。当贪心选择的规律性显而易见时，我们可以跳过动态规划的过程，直接使用贪心算法的设计方法。