循序渐进，搞懂什么是贪心算法

循序渐进，搞懂什么是贪心算法

贪心算法简介

贪心算法（greedy algorithm）又称贪婪算法，指在求解最优化问题时，每一步都选择在当前状态下最好或最优的策略，从而逐步推导出最优解的算法。

贪心算法不从整体最优上加以考虑，它所做出的选择只是局部最优选择。这种策略的显著特点是“目光短浅”，只看重眼前最好的选择，而不考虑更长远的结果。因此，贪心算法不是对所有问题都能得到整体最优的解。对于一些问题，它只能得到局部最优解，局部最优解并不一定是整体最优解，不过，通常是近似最优解。

贪心算法的典型应用包含：部分背包问题、霍夫曼编码（huffman coding）、最小生成树（普利姆算法，prim’s algorithm）、单源最短路径问题（迪杰斯特拉算法，Dijkstra’s algorithm）等。

贪心算法的关键是构造适合的贪心策略。贪心算法执行时根据贪心策略做出最优选择，不考虑各种可能的情况，省去了穷尽所有可能的选项而耗费的时间。因此贪心算法的运行效率高，运行时间较短。

贪心算法的一般求解步骤

贪心算法没有固定的解题套路，不过对一般情况，使用贪心算法，需要先对问题进行分析，可以参考如下的一般求解步骤。

1. 问题定义：明确问题的输入、输出和目标。

2. 状态定义：将问题分解为多个阶段，每个阶段都有一个状态。状态通常由问题的某些属性表示。

3. 确定贪心策略：在每个阶段，根据当前状态选择最优决策，以期望达到全局最优解。这个最优决策通常是最优子结构的一部分，问题的最优解可以通过其子问题的最优解来获得，则问题具有最优子结构，这意味着每个阶段的最优决策都是全局最优解的一部分。

4. 代码实现：根据上述步骤设计贪心算法，编写代码。通常，贪心算法包括一个循环，每次循环中都选择当前最优决策，并更新状态。

5. 算法分析：分析贪心算法的正确性和可行性。

贪心算法实现举例

贪心算法最简单易懂的应用是部分背包问题，下面直接看一个例子。

假设有一个能装下50磅重的背包，有5件不同的物品，它们的重量分别为[5, 10, 30, 20, 5]，价值分别为[80, 200, 300, 150, 30]，这5件物品都可以按每磅获取其中的一部分。为了使背包装下的物品价值最高，应该在背包中装哪些物品？最高价值是多少？

def part_backpack(weight_bp, weights, values):
    """部分背包问题"""
    # 计算单价并按从高到低排序
    unit_value = []
    for i in range(len(weights)):
        unit_value.append((f'w{i+1}', weights[i], values[i]/weights[i]))
    unit_value = sorted(unit_value, key=lambda x: x[2], reverse=True)
    # 开始贪心选择，优先选单价更高的物品
    result = []
    i = 0
    # 能全部装下的物品
    while i < len(unit_value):
        if unit_value[i][1] > weight_bp:
            break
        weight_bp -= unit_value[i][1]
        result.append(unit_value[i])
        i += 1
    # 能部分装下的物品
    if i < len(unit_value):
        part_item = list(unit_value[i])
        part_item[1] = weight_bp
        result.append(tuple(part_item))
    # 计算获得的最大价值
    max_value = sum(r[1]*r[2] for r in result)
    return result, max_value


weight_bp = 50
weights = [5, 10, 30, 20, 5]
values = [80, 200, 300, 150, 30]
result, max_value = part_backpack(weight_bp, weights, values)
print(result)
print('最大价值：', max_value)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

Output:

[('w2', 10, 20.0), ('w1', 5, 16.0), ('w3', 30, 10.0), ('w4', 5, 7.5)]
最大价值： 617.5
1
2

问题要求在5种不同重量和价值的物品中选择一部分装进背包，使最终装下的物品总价值最高。所以问题的输入就是背包容量、每件物品的重量和价值，输出就是每件物品装了多少，最终装进背包的总价值是多少，目标是使背包里装下的物品总价值最高。

要使总价值最高，最直观的方式就是优先装单位重量价值最高的物品，首先计算每件物品的单价（每磅的价值），贪心策略就是优先选择单价更高的物品。每往背包里装一样物品，都判断当前的背包是否已经装满，判断下一件物品是否可以装进背包，以及下一件物品是全部装进背包还是部分装进背包。这就是状态的定义和更新。

在上面的例子中，计算每件物品的单价后，将物品按单价从高到低排序，这样可以依次往背包里装单价排序靠前的物品。如果前面的物品重量小于背包容量，可以全部被装进背包，当背包剩余的容量越来越小，如果剩余容量小于背包外单价最高的物品重量，则该物品不能被全部装下，但可以被部分装下，此时将该物品的一部分装进背包，把背包填满（也可能装完某件物品时背包容量刚好为0）。装满背包后，记录装下了哪些物品，计算物品的总价值，得到问题的答案。

背包问题分为0-1背包问题和部分背包问题，如果每件物品都是一个整体，要么被装进背包，要么不被装进背包，这种要么装要么不装的情况被称为0-1背包问题。如果每件物品都可以被部分装进背包，如上面的例子每件物品都可以按磅“散装”，这种物品可以被拆分的情况被称为部分背包问题。

《算法导论》进行了论证，贪心算法不适用于0-1背包问题，但适用于部分背包问题。因为在0-1背包问题中，按贪心策略取物品不一定能填满背包，空余的空间会拉低物品的平均价值，从而导致贪心算法的结果只是次优解。而部分背包问题中，背包总是能被装满，按贪心策略取物品，总是能得到最优解。本文后面附上《算法导论》中的贪心算法的部分内容。

《算法导论》中的贪心算法

贪心算法是通过做一系列的选择来给出某一问题的最优解。对算法中的每一个决策点，做一个当时（看起来是）最佳的选择。这种启发式策略并不是总能产生出最优解，但它常常能给出最优解。

在实际设计贪心算法时，通常直接做出贪心选择来构造子结构，以产生一个待优化解决的子问题，或者，根据贪心选择来构造最优子结构。

更一般地，可以根据如下步骤来设计贪心算法：

1. 将优化问题转换成这样的一个问题，即先做出选择，再解决剩下的一个子问题。
2. 证明原问题总是有一个最优解是做贪心选择得到的，从而说明贪心选择的安全。
3. 说明在做出贪心选择后，剩余的子问题具有这样一个性质。即如果将子问题的最优解和我们所做的贪心选择联合起来，可以得出原问题的一个最优解。

贪心算法是否能够解决一个特定的最优化问题？一般来说不是，但是贪心选择性质和最优子结构是两个关键的特点。如果我们能够证明问题具有这些特点，那么就可以设计出它的一个贪心算法。

贪心选择性质

第一个关键特点是贪心选择性质，一个全局最优解可以通过局部最优（贪心）选择来达到。换句话说，当考虑做何选择时，我们只考虑当前问题最佳的选择而不考虑子问题的结果。

这一点是贪心算法不同于动态规划之处。在动态规划中，每一步都要做出选择，但是这些选择依赖于子问题的解。因此，解动态规划问题一般是自底向上，从小子问题处理至大子问题。在贪心算法中，我们所做的总是当前看似最佳的选择，然后再解决选择之后所出现的子问题。贪心算法所做的当前选择可能要依赖于已经做出的所有选择，但不依赖于有待做出的选择或子问题的解。因此，不像动态规划方法那样自底向上地解决子问题，贪心策略通常是自顶向下地做的，一个一个地做出贪心选择，不断地将给定的问题实例规约为更小的问题。

当然，我们必须证明在每一步所做的贪心选择最终能产生一个全局最优解，这也正是需要技巧的所在。一般来说，在证明中先考察一个全局最优解，然后证明可对该解加以修改，使其采用贪心选择，这个选择将原问题变为一个相似的、但更小的问题。

贪心选择性质在面对子问题做出选择时，通常能帮助我们提高效率，通常对数据进行处理或选用合适的数据结构（优先队列），能够使贪心选择更加快速，因而产生出一个高效的算法。

最优子结构

对一个问题来说，如果它的一个最优解包含了其子问题的最优解，则称该问题具有最优子结构。这个性质是用来对动态规划以及贪心算法的可应用性进行评价的关键一点。基于对最优子结构的观察，我们能够写出描述一个最优解值的递归式。

在贪心算法中使用最优子结构时，通常是用更直接的方式。假设在原问题中做了一个贪心选择而得到了一个子问题，真正要做的是证明将此子问题的最优解与所做的贪心选择合并后，的确可以得到原问题的一个最优解。这个方案意味着要对子问题采用归纳法，来证明每个步骤中所做的贪心选择最终会产生一个最优解。

贪心法与动态规划

因为贪心法和动态规划都利用了最优子结构性质，故人们往往会在贪心解足以解决问题的场合下，给出一个动态规划解，或者在需要动态规划方法的场合下使用贪心方法。为说明这两种算法之间的细微区别，我们来考察一个经典最优化问题的两种变形。

0-1背包问题是这样的：有一个贼在偷窃一家商店时发现有n件物品，第i件物品值v_i元，重w_i磅。此处v_i和w_i都是整数。他希望带走的东西越值钱越好，但他的背包中至多只能装下W磅的东西，W为一整数。应该带走哪几样东西？（这个问题之所以称之为0-1背包问题，是因为每件物品或被带走，或被留下，小偷不能只带走某个物品的一部分或带走两次以上的同一物品。）

部分背包问题中，场景等与上面问题一样，但是窃贼可以带走物品的一部分，而不必作出0-1的二分选择。可以把0-1背包问题的一件物品想象成一个金锭，而部分背包问题中的一件物品则更像金粉。

两种背包问题都具有最优子结构性质。对0-1背包问题，考虑重量至多为W磅的最值钱的一包东西。如果我们从中去掉物品j，余下的必须是窃贼从除j以外的n-1件物品中，可以带走的重量至多为W-w_j的最值钱的一包东西。对部分背包问题，考虑如果我们从最优货物中去掉某物品j的重量w，则余下的货物必须是窃贼可以从n-1件原有物品和物品j的w_j-w磅重中可带走的、重量至多为W-w的、最值钱的一包东西。

虽然这两个问题非常相似，但部分背包问题可用贪心策略来解决，而0-1背包问题却不行。为解决部分背包问题，先对每件物品计算其每磅的价值v_i/w_i，按照一种贪心策略，窃贼开始时对具有最大每磅价值的物品尽量多拿一些。如果他拿完了该物品而仍可以取一些其他物品时，他就再取具有次大的每磅价值的物品，一直持续下去，直到不能再取为止。这样，通过按每磅价值来对所有物品排序，贪心算法就可以以O(nlogn)时间运行。

为搞清楚为什么这种贪心策略不适用于0-1背包问题，让我们来看一个该问题的实例。总共有三件物品，背包可容纳50磅重的东西，物品1重10磅，价值60元，物品2重20磅，价值100元，物品3重30磅，价值120元。这样，物品1每磅6元，大于物品2的每磅5元和物品3的每磅4元，按照贪心策略的话就会最先取物品1，然而，经过分析，最优解取的是物品2和3，留下了物品1，两种包含物品1的可能解都是次优的。

对于部分背包问题，在按照贪心策略先取物品1以后，还可以取物品2，取物品3的一部分，确实可以产生一个最优解。在0-1背包问题中不应取物品1的原因在于这样无法将背包填满，空余的空间就降低了他的货物的有效每磅价值。在0-1背包问题中，当我们在考虑是否要把一件物品加到背包中时，必须对把该物品加进去的子问题的解与不取该物品的子问题的解进行比较。由这种方式形成的问题导致了许多重叠子问题（这是动态规划的一个特点）。所以，我们可以用动态规划来解决0-1背包问题。

---

相关阅读：

循序渐进，搞懂什么是动态规划