跳转至

貪心

本頁面將簡要介紹貪心算法。

引入

貪心算法（英語：greedy algorithm），是用計算機來模擬一個「貪心」的人做出決策的過程。這個人十分貪婪，每一步行動總是按某種指標選取最優的操作。而且他目光短淺，總是隻看眼前，並不考慮以後可能造成的影響。

可想而知，並不是所有的時候貪心法都能獲得最優解，所以一般使用貪心法的時候，都要確保自己能證明其正確性。

解釋

適用範圍

貪心算法在有最優子結構的問題中尤為有效。最優子結構的意思是問題能夠分解成子問題來解決，子問題的最優解能遞推到最終問題的最優解。1

證明

貪心算法有兩種證明方法：反證法和歸納法。一般情況下，一道題只會用到其中的一種方法來證明。

  1. 反證法：如果交換方案中任意兩個元素/相鄰的兩個元素後，答案不會變得更好，那麼可以推定目前的解已經是最優解了。
  2. 歸納法：先算得出邊界情況（例如 \(n = 1\)）的最優解 \(F_1\)，然後再證明：對於每個 \(n\)，\(F_{n+1}\) 都可以由 \(F_{n}\) 推導出結果。

要點

常見題型

在提高組難度以下的題目中，最常見的貪心有兩種。

  • 「我們將 XXX 按照某某順序排序，然後按某種順序（例如從小到大）選擇。」。
  • 「我們每次都取 XXX 中最大/小的東西，並更新 XXX。」（有時「XXX 中最大/小的東西」可以優化，比如用優先隊列維護）

二者的區別在於一種是離線的，先處理後選擇；一種是在線的，邊處理邊選擇。

排序解法

用排序法常見的情況是輸入一個包含幾個（一般一到兩個）權值的數組，通過排序然後遍歷模擬計算的方法求出最優值。

後悔解法

思路是無論當前的選項是否最優都接受，然後進行比較，如果選擇之後不是最優了，則反悔，捨棄掉這個選項；否則，正式接受。如此往復。

區別

與動態規劃的區別

貪心算法與動態規劃的不同在於它對每個子問題的解決方案都做出選擇，不能回退。動態規劃則會保存以前的運算結果，並根據以前的結果對當前進行選擇，有回退功能。

例題詳解

鄰項交換法的例題

NOIP 2012 國王遊戲

恰逢 H 國國慶，國王邀請 n 位大臣來玩一個有獎遊戲。首先，他讓每個大臣在左、右手上面分別寫下一個整數，國王自己也在左、右手上各寫一個整數。然後，讓這 n 位大臣排成一排，國王站在隊伍的最前面。排好隊後，所有的大臣都會獲得國王獎賞的若干金幣，每位大臣獲得的金幣數分別是：排在該大臣前面的所有人的左手上的數的乘積除以他自己右手上的數，然後向下取整得到的結果。

國王不希望某一個大臣獲得特別多的獎賞，所以他想請你幫他重新安排一下隊伍的順序，使得獲得獎賞最多的大臣，所獲獎賞儘可能的少。注意，國王的位置始終在隊伍的最前面。

解題思路

設排序後第 \(i\) 個大臣左右手上的數分別為 \(a_i, b_i\)。考慮通過鄰項交換法推導貪心策略。

用 \(s\) 表示第 \(i\) 個大臣前面所有人的 \(a_i\) 的乘積，那麼第 \(i\) 個大臣得到的獎賞就是 \(\dfrac{s} {b_i}\)，第 \(i + 1\) 個大臣得到的獎賞就是 \(\dfrac{s \cdot a_i} {b_{i+1}}\)。

如果我們交換第 \(i\) 個大臣與第 \(i + 1\) 個大臣，那麼此時的第 \(i\) 個大臣得到的獎賞就是 \(\dfrac{s} {b_{i+1}}\)，第 \(i + 1\) 個大臣得到的獎賞就是 \(\dfrac{s \cdot a_{i+1}} {b_i}\)。

如果交換前更優當且僅當

\[ \max \left(\dfrac{s} {b_i}, \dfrac{s \cdot a_i} {b_{i+1}}\right) < \max \left(\dfrac{s} {b_{i+1}}, \dfrac{s \cdot a_{i+1}} {b_i}\right) \]

提取出相同的 \(s\) 並約分得到

\[ \max \left(\dfrac{1} {b_i}, \dfrac{a_i} {b_{i+1}}\right) < \max \left(\dfrac{1} {b_{i+1}}, \dfrac{a_{i+1}} {b_i}\right) \]

然後分式化成整式得到

\[ \max (b_{i+1}, a_i\cdot b_i) < \max (b_i, a_{i+1}\cdot b_{i+1}) \]

實現的時候我們將輸入的兩個數用一個結構體來保存並重載運算符：

1
2
3
4
5
6
7
struct uv {
  int a, b;

  bool operator<(const uv &x) const {
    return max(x.b, a * b) < max(b, x.a * x.b);
  }
};

後悔法的例題

「USACO09OPEN」工作調度 Work Scheduling

約翰的工作日從 \(0\) 時刻開始，有 \(10^9\) 個單位時間。在任一單位時間，他都可以選擇編號 \(1\) 到 \(N\) 的 \(N(1 \leq N \leq 10^5)\) 項工作中的任意一項工作來完成。工作 \(i\) 的截止時間是 \(D_i(1 \leq D_i \leq 10^9)\)，完成後獲利是 \(P_i( 1\leq P_i\leq 10^9 )\)。在給定的工作利潤和截止時間下，求約翰能夠獲得的利潤最大為多少。

解題思路
  1. 先假設每一項工作都做，將各項工作按截止時間排序後入隊；
  2. 在判斷第 i 項工作做與不做時，若其截至時間符合條件，則將其與隊中報酬最小的元素比較，若第 i 項工作報酬較高（後悔），則 ans += a[i].p - q.top()。
    用優先隊列（小根堆）來維護隊首元素最小。
  3. 當 a[i].d<=q.size() 可以這麼理解從 0 開始到 a[i].d 這個時間段只能做 a[i].d 個任務，而若 q.size()>=a[i].d 説明完成 q.size() 個任務時間大於等於 a[i].d 的時間，所以當第 i 個任務獲利比較大的時候應該把最小的任務從優先級隊列中換出。
參考代碼 
 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
37
38
39
40
41
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

struct f {
  long long d;
  long long p;
} a[100005];

bool cmp(f A, f B) { return A.d < B.d; }

priority_queue<long long, vector<long long>, greater<long long> >
    q;  // 小根堆维护最小值

int main() {
  long long n, i;
  cin >> n;
  for (i = 1; i <= n; i++) {
    scanf("%lld%lld", &a[i].d, &a[i].p);
  }
  sort(a + 1, a + n + 1, cmp);
  long long ans = 0;
  for (i = 1; i <= n; i++) {
    if (a[i].d <= (int)q.size()) {  // 超过截止时间
      if (q.top() < a[i].p) {       // 后悔
        ans += a[i].p - q.top();
        q.pop();
        q.push(a[i].p);
      }
    } else {  // 直接加入队列
      ans += a[i].p;
      q.push(a[i].p);
    }
  }
  cout << ans << endl;
  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
from collections import defaultdict
from heapq import heappush, heappop

a = defaultdict(list)
for _ in range(int(input())):
    d, p = map(int, input().split())
    a[d].append(p)  # 存放对应时间的收益

ans = 0  # 记录总收益
q = []  # 小根堆维护最小值
l = sorted(a.keys(), reverse=True)
for i, j in zip(l, l[1:] + [0]):
    for k in a.pop(i):
        heappush(q, ~k)
    for _ in range(i - j):
        if q:  # 从堆中取出收益最多的工作
            ans += ~heappop(q)
        else:  # 堆为空时退出循环
            break
print(ans)
複雜度分析

  • 空間複雜度：當輸入 \(n\) 個任務時使用 \(n\) 個 \(a\) 數組元素，優先隊列中最差情況下會儲存 \(n\) 個元素，則空間複雜度為 \(O(n)\)。

  • 時間複雜度：std::sort 的時間複雜度為 \(O(n\log n)\)，維護優先隊列的時間複雜度為 \(O(n\log n)\)，綜上所述，時間複雜度為 \(O(n\log n)\)。

習題

參考資料與註釋

  1. 貪心算法 - 維基百科，自由的百科全書 ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用