貪欲なアルゴリズム（greedy）入門

2020年1月19日貪欲法入門,競プロ,貪欲法

貪欲なアルゴリズムとは以下のような性質を持つアルゴリズムのことを言います。

  • その場での最善の手を選ぶことを繰り返す

貪欲法を用いたアルゴリズムは、実装が簡単な上に応用範囲が広いので非常に重要です。

大まかに二種類に大別され、

  • 貪欲法で求まる解が、最適解と一致する
  • 貪欲法で求まる解が、最適解ではなくズレている

となります。「前者だと思っていたら実は後者で、貪欲法を用いるべきでないところで使用してしまった」などということも多いので注意が必要です。

貪欲法が最適解となるのは、自明なときもあれば、そうでないときもあります。可能なら本当に正しいかの証明まで考えてみると良いでしょう。今回は本質ではないので省略します。

この記事では、前者の最適解と一致する場合の例題を確認して、貪欲法に慣れることを目指します。

例題：硬貨の選び方

AOJ 0521 Change を解いてみましょう

問題概要

複数の支払う金額が与えられる。それぞれに対して1000円を支払った時、お釣りに含まれる硬貨の枚数の最小値を求めよ。
お釣りに使える硬貨は、500, 100, 50, 10, 5, 1円がそれぞれ十分な数ある。

考え方

まずはお釣りの金額を計算します。

なるべく金額の大きいものを多く使うようにすれば、硬貨の枚数が少なくて済みます。500円を多く使い、１円を使う数は少なくなるようにすれば良いです。

よって貪欲的に、

  1. お釣りを超えない範囲で、一番金額の大きい硬貨を使うことにする
  2. 1 で使った金額分だけお釣りを減らす

という操作を何度も繰り返すと、選択してきた硬貨が最適な選び方になっています。

プログラム例

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> pays;
    while (1) {
        int tmp;
        cin >> tmp;
        if (tmp == 0) {
            break;
        } else {
            pays.push_back(tmp);
        }
    }

    vector<int> coins = {500, 100, 50, 10, 5, 1};
    for (auto pay : pays) {
        int back = 1000 - pay; // お釣り
        int ans = 0;
        for (auto coin : coins) {
            int use = back / coin; // coin円 を使用する枚数
            back -= coin * use;
            ans += use;
        }
        cout << ans << endl;
    }
    return 0;
}

例題：区間スケジューリング問題

AtCoder キーエンスプログラミングコンテスト2020 B – Robot Arms を解いて見ましょう。

超典型問題です。

問題概要

N個の開区間があり、それぞれ 始点 \(X_i – L_i\) から終点\(X_i + L_i\)となっています。重ならないように区間を選ぶとき、最大何個まで選べるか答えてください。

考え方

ありがちな間違いとしては、「選べる物の中で始点が最小のものを選択する」ように貪欲に区間を選択していくことが考えられます。

この方法だと最適な選び方とならない例があります。例えば、始点が一番小さく終点が一番大きいような区間が存在した時は、他の小さい区間がいくらたくさんあっても選ぶことができません。

正しいアルゴリズムは、「選べる物の中で終点が最小のものを選択する」ような貪欲法になります。

プログラム例

#include <bits/stdc++.h>
using namespace std;
int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);

    int N;
    cin >> N;
    vector<int> X(N), L(N);
    for (int i = 0; i < N; i++) {
        cin >> X.at(i) >> L.at(i);
    }

    vector<pair<int, int>> p(N);
    for (int i = 0; i < N; i++) {
        p[i].first = X[i] + L[i]; // 終端を先に入れておく
        p[i].second = X[i] - L[i];
    }

    sort(p.begin(), p.end()); // 終端を優先にソート

    int ans = 1;
    int t = p[0].first; // t:=現在までに選択した区間の中で一番後ろの点
    for (int i = 1; i < N; i++) {
        if (t <= p[i].second) {
            ans++;
            t = p[i].first;
        }
    }

    cout << ans << endl;

    return 0;
}

貪欲法入門,競プロ,貪欲法