Skip to content

Greedy

This page provides a brief introduction to greedy algorithms.

Introduction

A greedy algorithm (English: greedy algorithm) is a method that simulates a "greedy" person making decisions using a computer. This person is extremely greedy, always choosing the optimal operation at each step according to some metric. Moreover, they are short-sighted, focusing only on the immediate situation without considering potential future impacts.

As one might expect, greedy algorithms do not always yield the optimal solution. Therefore, when using a greedy approach, it is generally necessary to ensure that its correctness can be proven.

Explanation

Applicability

Greedy algorithms are particularly effective for problems with optimal substructure. Optimal substructure means that the problem can be decomposed into subproblems to solve, and the optimal solution of the subproblems can be recursively applied to the optimal solution of the final problem.1

Proof

There are two main methods to prove the correctness of a greedy algorithm: proof by contradiction and proof by induction. Typically, only one of these methods is used to prove a given problem.

  1. Proof by contradiction: If swapping any two elements (or two adjacent elements) in the solution does not yield a better result, then it can be inferred that the current solution is already optimal.
  2. Proof by induction: First, compute the optimal solution for the base case (e.g., \(n = 1\)), denoted as \(F_1\). Then prove that for each \(n\), \(F_{n+1}\) can be derived from \(F_{n}\).

Key Points

Common Problem Types

In problems below the advanced level, the two most common greedy strategies are:

  • "We sort XXX according to a certain order, then select in some order (e.g., from smallest to largest)."
  • "We always take the largest/smallest element from XXX and update XXX." (Sometimes "the largest/smallest element in XXX" can be optimized, e.g., using a priority queue to maintain it.)

The difference between the two is that the former is offline (process first, then select), while the latter is online (process and select simultaneously).

Sorting-Based Solutions

Using sorting is common when the input is an array containing several (usually one or two) weights. The optimal value is calculated by sorting and then traversing the array to simulate the process.

Regret-Based Solutions

The idea is to always accept the current option, regardless of whether it is optimal, and then compare. If the choice later turns out not to be optimal, regret the decision and discard that option; otherwise, formally accept it. This process repeats.

Differences

Difference from Dynamic Programming

The difference between greedy algorithms and dynamic programming is that greedy algorithms make a choice for each subproblem and cannot backtrack. Dynamic programming, on the other hand, saves previous computation results and makes choices based on past results, allowing backtracking.

Example Problems Explained

Example of Adjacent Swapping Method

NOIP 2012 King's Game

It happened to be National Day in Kingdom H, and the king invited n ministers to play a prize game. First, he asked each minister to write an integer on their left and right hands, and the king also wrote an integer on his left and right hands. Then, the n ministers lined up in a row, with the king standing at the front of the line. After the line was formed, all ministers received a certain number of gold coins as a reward from the king. The number of gold coins each minister received was: the product of the numbers on the left hands of all people in front of that minister, divided by the number on his own right hand, rounded down.

The king did not want any minister to receive an exceptionally large reward, so he asked you to help rearrange the order of the line so that the minister who receives the most reward gets as little as possible. Note that the king's position is always at the front of the line.

Solution Idea

Let the numbers on the left and right hands of the \(i\)-th minister after sorting be \(a_i, b_i\). Consider deriving the greedy strategy using the adjacent swapping method.

Let \(s\) denote the product of the \(a_i\) values of all people in front of the \(i\)-th minister. Then the reward for the \(i\)-th minister is \(\dfrac{s} {b_i}\), and the reward for the \(i + 1\)-th minister is \(\dfrac{s \cdot a_i} {b_{i+1}}\).

If we swap the \(i\)-th minister and the \(i + 1\)-th minister, then the reward for the \(i\)-th minister becomes \(\dfrac{s} {b_{i+1}}\), and the reward for the \(i + 1\)-th minister becomes \(\dfrac{s \cdot a_{i+1}} {b_i}\).

The original order is better if and only if

\[ \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) \]

Extract the common factor \(s\) and simplify to get

\[ \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) \]

Convert the fractions to integers to obtain

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

In implementation, we store the two input numbers in a structure and overload the operator:

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);
  }
};

Example of Regret-Based Method

「USACO09OPEN」Work Scheduling

John's workday starts at time \(0\) and has \(10^9\) unit times. At any unit time, he can choose any one of the \(N(1 \leq N \leq 10^5)\) jobs numbered \(1\) to \(N\) to complete. Job \(i\) has a deadline \(D_i(1 \leq D_i \leq 10^9)\) and a profit \(P_i( 1\leq P_i\leq 10^9 )\) upon completion. Given the job profits and deadlines, determine the maximum profit John can achieve.

Solution Idea
  1. First, assume all jobs are done. Sort the jobs by deadline and enqueue them.
  2. When deciding whether to do the i-th job, if its deadline meets the condition, compare it with the job with the smallest reward in the queue. If the i-th job has a higher reward (regret), then ans += a[i].p - q.top().
    Use a priority queue (min-heap) to maintain the smallest element at the front.
  3. The condition a[i].d<=q.size() can be understood as: from time 0 to a[i].d, only a[i].d tasks can be completed. If q.size()>=a[i].d, it means the time to complete q.size() tasks is greater than or equal to the time until a[i].d. Therefore, when the i-th task has a relatively high profit, the smallest task should be replaced in the priority queue.
Reference Code 
 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
#include <algorithm>
#include <cmath>
#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; }

// Min-heap to maintain the smallest value
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++) {
    cin >> 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()) {  // Exceeds deadline
      if (q.top() < a[i].p) {       // Regret (replace)
        ans += a[i].p - q.top();
        q.pop();
        q.push(a[i].p);
      }
    } else {  // Directly add to queue
      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)  # Store earnings corresponding to time

ans = 0  # Record total earnings
q = []  # Min-heap to maintain minimum values
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:  # Take the job with the highest earnings from the heap
            ans += ~heappop(q)
        else:  # Exit loop when heap is empty
            break
print(ans)
Complexity Analysis
  • Space Complexity: When inputting \(n\) tasks, \(n\) elements of array \(a\) are used. In the worst case, the priority queue stores \(n\) elements, so the space complexity is \(O(n)\).
  • Time Complexity: std::sort has a time complexity of \(O(n\log n)\), and maintaining the priority queue has a time complexity of \(O(n\log n)\). In summary, the time complexity is \(O(n\log n)\).

Exercises

References and Notes

  1. Greedy algorithm - Wikipedia ↩

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