“1手先だけ”を考える「貪欲法」

貪欲法は、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 通りしかありません。したがって、金額が大きい紙幣から順に支払うのが最適です。