何为贪心？

• 贪心算法在解决问题的策略上目光短浅，只根据当前已有的信息就作出选择（下一步的选择总是在当前看来收敛最快和效果最明显的那一个），而且一旦做出了选择，不管将来有什么结果，这个选择策略都不会改变（以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题）。
• 贪心算法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。
• 贪心算法对于大部分的优化问题都能产生最优解（如单源最短路径问题，最小生成树等），但不能总获得整体最优解，通常可以获得近似最优解。
• 贪心策略一旦经过证明成立后，它就是一种高效的算法。

一般流程

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

  // C 是问题的输入集合即候选集合 Greedy(C) { // 初始解集合 S 为空集 S = {}; // 集合 S 没能构成问题的一个解 while(not solution(S)) { // 在候选集合 C 中做贪心选择 x = select(C); // 判断集合 S 加入 x 后的解是否可行 if(feasible(S, x)) { S += {x}; C -= {x}; } } return S; }

• 候选集合 C：为了构造问题的解决方案，有一个候选集合 C 作为问题的可能解，即问题的最终解均取自于候选集合 C。
• 解集合 S：随着贪心选择的进行，解集和 S 不断扩展，直到构成一个满足问题的完整解。
• 解决函数 solution：检查解集合 S 是否构成问题的完整解？
• 选择函数 select：贪心策略，关键的一步。它指出哪个候选对象最有希望构成问题的解，选择函数通常与目标函数，即求解的问题有关。
• 可行函数 feasible：检查解集合 S 加入候选对象后是否依旧可行？即解集合扩展后是否满足约束条件。

贪心算法可行的基本要素

是否可用贪心算法求解？

• 子问题：为了解决某一优化问题（目标函数），需要依次作出 n 个决策 $D_1, D_2, …, D_n$，对于任何一次决策 $D_k, 1 \lt k \lt n$，以 $D_k$ 作为问题的初始状态，来进行以后的决策 $D_{k+1}$…，这样的每次决策就成为是原问题的一个子问题；贪心算法以迭代的方式作出相继的贪心选择，每做一次贪心选择，就将所求问题简化成规模更小的子问题。
• ① 贪心选择性质
  • 所求问题的整体最优解可以通过一系列局部最优的选择得到，即对于一个具体问题，要确定它是否具有贪心选择的性质，必须证明每一步所做的贪心选择最终导致问题的整体最优解。
  • 当考虑当前问题的做何种选择的时候，只需考虑对当前问题最佳的选择而不用考虑子问题的结果。
• ② 最优子结构性质（关键基本元素）
  • 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

活动选择问题

• 问题描述

  假设有一个需要使用某个资源的$n$个活动组成的集合 $S= \verb|{|a1，a2，···，an \verb|}|$，该资源每次只能由一个活动占用。每个活动 $a[i]$ 都有一个开始时间 $s[i]$ 和结束时间 $f[i]$，且 $0 \leq s[i] \lt f[i] \lt ∞$。一旦被选择后，活动 $a[i]$ 就占据半开时间区间 $[s[i], f[i])$。若时间区间 $[s[i], f[i])$ 与区间 $[s[j], f[j])$ 互不重叠，则称活动 $a[i] $与活动 $a[j]$ 是兼容的。也就是说，当 $s[i] \geq f[j]$ 或 $s[j] \geq f[i]$ 时，活动 $a[i]$ 与活动 $a[j]$ 兼容。活动选择问题就是要选择一个由兼容活动构成的最大集合。

• DP策略：贪心是特殊的 DP
  • Step1：活动选择问题就是要选择一个由兼容活动构成的最大集合，子问题是什么，兼容活动集合，这样的子问题有 $2^n$。所以我们才用 DP 来优化它，如果子问题的最优解可以构造成原问题的最优解，那么此问题就具有② 最优子结构性质。
    • 定义 $S[i, j] = \verb|{|a[k]∈S: f[i] \leq s[k] < f[k] \leq s[j] \verb|}|$，$S$ 是所有活动集合。$S[i, j]$ 就是原问题集合 $S$ 的子问题，其中的每个活动都是在活动 $a[i]$ 结束之后开始，且在 $a[j]$ 开始之前结束，更重要的是 $S[i, j]$ 中的活动都要相互兼容。
    • 为了表示完整的问题集合，虚构两个活动 $a[0], a[n+1], f[0]=0, s[n+1]=∞$，这样 $S=S[0，n+1]$。
  • Step2：为了减少问题的处理量，给所有活动按结束时间递增的顺序排序。这样的话如果 $i \geq j, S[i, j] = ∅$。
    • 假设有一个 $a[k]∈S[i,j], 则 f[i] \leq s[k] \lt f[k] \leq s[j]$。说明 $a[i]$ 活动排在 $a[j]$ 活动前面，也即是 $i \lt j$，这与 $i \geq j$ 矛盾。所以来说，如果将活动按结束时间非递减排序的话，则子问题就是 $S[i, j]$，$0 \leq i \lt j \leq n+1$，其他的 $S[i, j]$ 是空集。
  • Step3：针对于 $S[i, j]$ 中的 $a[k]$，我们把子问题分成 $S[i, k], S[k, j]$ 和 $a[k]$。则 $S[i, j]$ 的最优解就是 $S[i, k]$ 的最优解加上 $S[k, j]$ 的最优解捎带一个 $a[k]$ 的并集。设 $C[i, j]$ 是 $S[i, j]$ 的最优解，即是 $S[i, j]$ 中最大兼容活动数。
    $$ C[i, j] = \begin{cases} 0, S[i, j] = \emptyset \cr max_{i < k < j} \verb|{| C[i, k]+C[k, j]+1 \verb|}|, S[i, j] != \emptyset \end{cases}$$

• 1 2 3 4 5 6 7 8 9 10 11 12

  // 将活动按结束时间非递减排序 Activity-Selector(s, f, i, j) { m <-- i+1 // find the first activity in S[i,j] while m<j and s[m]<f[i] {} if(m<j) return {a[m]} ∪ Activity-Selector(s, f, m, j) else return ∅ }

• 贪心策略：最早结束的活动肯定就是当前子问题的最优活动。对于任何非空 $S[i,j]$，设 $a[m]$ 是 $S[i, j]$ 中最早结束的一个活动，$f[m] = min{f[k]: a[k]∈S[i, j]}$，则
  • ① 贪心选择性质（贪心策略是安全的）：活动 $a[m]$ 被包含在 $S[i, j]$ 的一个（可能有多个）最大兼容活动的子集中
    • 假设 $a[k]$ 是 $S[i, j]$ 最优解 $C[i, j]$ 的第一个活动（排序之后），如果 $a[m] = a[k]$，结论得证
    • 如果 $a[m], a[k]$ 不相等，那么就用 $a[m]$ 替换 $a[k]$（因为 $a[m]$ 是最早结束的活动，替换之后肯定和其他的兼容），原问题的最大兼容活动数目没变，结论得证。
  • 最早结束的活动 $a[m]$ 肯定就是当前子问题的最优活动！你选择了 $a[m]$，那么剩余问题的最优解就是 $S[m, j]$ 的最优解。
  • 这就是贪心算法，每次都选择当前最好的选择，意思就是已经选定是最优活动，那么之后选择的最优要和之前选定的活动兼容，这样每次选择的活动都是和之前兼容的，那所有的活动也就只是考虑一次而已。
• Greedy（贪心） vs DP（动态规划）
  • DP 和贪心的区别就是做选择的时候贪心所做出的选择是当前最佳，要依赖已经做出的所有贪心选择，而不依赖有待于做出选择的子问题的解。而 DP 具有无后效性，未来与过去无关，当前的状态是此前历史的一个完整总结，不会依赖已经得到子问题的解，只是和以后的子问题有关系，这点和贪心刚好相反。
  • DP 是通过小问题来得到大问题的解，而贪心是一次一次做出贪心选择，然后不断将给定的问题规约为更小的子问题。DP要自底向上，贪心可以自顶向下地解决问题。
  • DP 还具有重叠子问题的性质，从上面也可以看出来，这点是贪心不具备的。
• 活动时间安排的例题
  • Sicily1001. 会议安排

    N个会议要同时举行，参会人数分别为$A[0], A[1], …, A[N-1]$. 现有M个会议室，会议室可容纳人数分别为$B[0], B[1], …, B[M-1]$. 当$A[i]<=B[j]$时，可以把会议$i$安排在会议室$j$，每间会议室最多安排一个会议，每个会议最多只能安排一个会议室. 求最多安排多少个会议？

    • 贪心策略：参会人数少的会议先安排，怎么安排呢？安排到能满足容纳人数的最小的会议室。

• 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 34 35 36

  // Problem#: 20617 // Submission#: 5148744 // The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License // URI: http://creativecommons.org/licenses/by-nc-sa/3.0/ // All Copyright reserved by Informatic Lab of Sun Yat-sen University class Solution { public: int assignConferenceRoom(vector<int>& A, vector<int>& B) { int conferenceNum = A.size(); int roomNum = B.size(); if(conferenceNum==0 || roomNum==0) { return 0; } // sort conference in conferee increasing order sort(A.begin(), A.end(), less<int>()); // sort room in room's size increasing order sort(B.begin(), B.end(), less<int>()); int conferenceOpenNum = 0; int bIdx=0; for(int aIdx=0; aIdx<conferenceNum; aIdx++) { while(bIdx<roomNum) { if(A[aIdx]<=B[bIdx++]) { conferenceOpenNum++; break; } } if(bIdx == roomNum) { break; } } return conferenceOpenNum; } };

其他几个经典问题

• 区间覆盖问题（近似活动选择问题）：多个区间，存在相互覆盖，要求去除多余的空间，使剩下的区间（不存在相互覆盖了）占用长度最大。
• 线段覆盖（lines cover）：在一维空间中告诉你 N 条线段的起始坐标和终止坐标，要求求出这些线段一共覆盖了多大的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// 优先选择：s[i] 由小到大排序
for(int pre=0, int cur=1; cur<size; cur++) {
  // 相邻线段不存在覆盖
  if(s[cur] >= f[pre]) {
    lineCover += f[cur] - s[cur];
    pre = cur;
  }
  // 存在相互覆盖
  else {
    // 不仅覆盖，还被包含，直接丢弃当前线段
    if(f[cur]<=f[pre]) {
      continue;
    }
    else {
      lineCover += f[cur] - s[pre];
      pre = cur;
    }
  }
}

• 数字组合问题：有 N 个正整数，使它们连接在一起成立最大的数字
  • 冒泡排序：冒泡条件 $\Longrightarrow$ 开头最大的数字
• 背包问题
  • 问题描述

    有一个背包，背包容量是$M$。有$N$个任意大小 $wi$，价值 $pi$ 的物品。要求尽可能让装入背包中的物品总价值最大，但不能超过背包总容量。
    目标函数： $\sum_i^N pi$最大
    约束条件：装入的物品总重量不超过背包容量：$\sum_i^N wi<=M$。

  • 根据贪心的策略
    • 每次挑选价值最大的物品装入背包，得到的结果是否最优？
    • 每次挑选所占重量最小的物品装入是否能得到最优解？
    • 每次选取单位重量价值最大的物品，成为解本题的策略。

References

• 五大常用算法之三：贪心算法
• HaHack：贪婪算法
• K神丶的专栏：贪心算法详解
• 活动选择问题：承续缘的信仰：贪心算法详解