貪欲法は、1 手先だけを考えることで答えを求めていくアルゴリズムです。リバーシの対戦に例えると、「最も多くのコマをひっくり返せる手」を打ち続けるようなイメージです。ただし、全ての問題に貪欲法が通用するとは限らず、10 手先を読んで初めて最適解が得られることもあります。では一体、どのような問題に貪欲法が有効なのでしょうか。

紙幣の問題

10000 円札・5000 円札・1000 円札を使って N 円ちょうどを支払うとき、最小何枚の紙幣が必要かを考えてみましょう。例えば N=37000 の場合、下図のように支払うと 6 枚必要であり、これが最小です。

皆さんも日常生活で支払時に考えたことがあるかもしれませんが、実は金額の大きい紙幣から“貪欲に”支払うと、枚数が最小になります。具体的には次の通りです。

  • 手順 1： 残り支払い金額が 10000 円未満になるまで、10000 円札を使って支払う。
  • 手順 2： 残り支払い金額が 5000 円未満になるまで、5000 円札を使って支払う。
  • 手順 3： 残りの金額を 1000 円札で支払う。

このアルゴリズムを Python で実装すると以下のようになります。ここで、手順 2 で支払う枚数は必ず 1 枚以下、手順 3 で支払う枚数は必ず 4 枚以下になります。

# 入力
N = int(input())

# 手順 1（A は支払う 10000 円札の枚数）
A = N // 10000
N -= A * 10000

# 手順 2（B は支払う 5000 円札の枚数）
B = N // 5000
N -= B * 5000

# 手順 3（C は支払う 1000 円札の枚数）
C = N // 1000
N -= C * 1000

# 出力
print(A + B + C)

紙幣の問題の証明

それでは、前述の貪欲法にのっとって支払うとき、どのような N でも合計枚数が最小になることを証明してみましょう。まず、次の性質が成り立ちます。

  • 5000 円札が 2 枚あった場合、これを 10000 円札に変えると合計枚数が減る
  • 1000 円札が 5 枚あった場合、これを 5000 円札に変えると合計枚数が減る

このことから、以下の条件のうち片方でも満たさない支払い方は最適ではないことが分かります。

  • 5000 円札を 1 枚以下使って支払う。
  • 1000 円札を 4 枚以下使って支払う。

一方、2 つの条件どちらも満たすようなものは、貪欲法にのっとって支払った場合の 1 通りしかありません。したがって、金額が大きい紙幣から順に支払うのが最適です。

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

もう一つの例として、以下のような「区間スケジューリング問題」も貪欲法で解くことが可能です。

今日は N 本の映画が上映されます。i 番目の映画は時刻 Li に開始し、時刻 Ri に終了します。最大何本の映画を最初から最後まで見ることができるかを求めてください。ただし、同時に複数の映画を見ることはできないものとします。

制約： 1 ≤ N ≤ 2000, 0 ≤ Li < Ri ≤ 86400

出典： アルゴリズムと数学 演習問題集 082 - Interval Scheduling Problem

直観的には、開始時刻の早い映画を優先的に選んでいく戦略が上手くいきそうに思えます。しかし、以下の図の例を考えてみましょう。

最適解は 3 本ですが、この方法では 2 本の映画しか見ることができません。ではどうすれば良いのでしょうか。

実は「今選べる中で終了時刻の一番早い映画を選び続ける」という戦略に従うと、最も多くの映画を見ることができます。前述の例でも、下図のように 3 本の映画を選べています。

このアルゴリズムで最適解が得られる理由は、終了時刻が早ければ早いほど次の選択肢が増えることから説明できます。したがって、以下のようなプログラムを書くと、正しい答えが得られます※。

# 入力
N = int(input())
L = [ None ] * N
R = [ None ] * N
for i in range(N):
    L[i], R[i] = map(int, input().split())

# 映画の選び方のシミュレーション
# 見られる映画の終了時刻の最小値 min_endtime は、最初 1000000 (INF で設定）のようなあり得ない値にセットする
INF = 1000000
current_time = 0  # current_time は現在時刻（直前に見た映画の終了時刻）
answer = 0
while True:
    min_endtime = INF
    for i in range(N):
        if L[i] >= current_time:
            min_endtime = min(min_endtime, R[i])
    if min_endtime == INF:
        break
    current_time = min_endtime
    answer += 1

# 答えの出力
print(answer)

貪欲法を使う際の注意点

問題によっては 1 手先のみを考える貪欲法で最適な答えが得られますが、そうではない問題もあります。例えば本稿の冒頭で紹介した「紙幣の問題」で、4000 円札・3000 円札・1000 円札のみが使えるケースを考えてみましょう。6000 円を支払うとき、以下のようになり、上手くいきません。

  • 貪欲法を使った場合： 3 枚（4000 円 + 1000 円 + 1000 円）
  • 最適な答え： 2 枚（3000 円 + 3000 円）

このため、貪欲法を使う際はアルゴリズムの正当性について考えることや、次回取り上げる「動的計画法」など、他のアルゴリズムも検討することが大切です。

※このアルゴリズムの計算量は O(N2) ですが、本連載の後半で紹介する「ソート」を使うと、計算量を O(N log N) に改善することができます。