貪欲法：お釣り問題が失敗する条件と区間スケジューリングの証明

2026年11月改訂： この記事は2021年に韓国語で書いた講座を、日本語向けに書き直したものです。当時のCの例を Apple clang 21（-Wall -Wextra -fsanitize=address,undefined）でコンパイルし直したところ、警告は出ませんでしたが、入力が空だとでたらめな枚数を表示するバグがありました。また「大きい硬貨が小さい硬貨の倍数でなければ貪欲法は使えない」「ナップサック問題に貪欲法を使う」という説明は半分しか正しくありませんでした。貪欲法とDPを同じ入力で比べた結果、区間スケジューリングの証明、貪欲法を使ってよいかの判断基準を加えています。

競技プログラミングや業務コードで「大きいものから取ればいいだろう」と書いて、一部の入力で答えが合わなかった人向けの記事です。結論を先に書くと、貪欲法が最適解を保証するのは貪欲選択性と最適部分構造の両方を示せるときだけです。証明が難しいときは、小さな入力範囲でDPや全探索と突き合わせるのがいちばん速い確認方法で、硬貨の場合は確認すべき範囲がかなり狭いこともわかります。

その場で最善を選び、後戻りしない

貪欲法（グリーディ法、Greedy Algorithm）は、選ぶたびにその時点でいちばん良く見えるものを取り、一度選んだものは取り消さずに答えを組み立てます。先を読まないので速く、実装も短く済みます。ただし、局所的な最善を積み重ねた結果が全体の最善になるかどうかは、問題ごとに確かめる必要があります。

定番の例がお釣りの問題です。硬貨が1円・7円・10円の3種類だとして、14円を最少枚数で払うとします。大きい硬貨から取ると10円1枚と1円4枚で5枚です。しかし7円2枚なら2枚で済みます。最初に10円を取った時点で、より良い答えへの道がふさがれたわけです。

2021年の例を動かし直す

2021年のコードは、金額から硬貨を1枚ずつ引いていく書き方でした。今の clang でも C・C++ どちらとしても警告なしでコンパイルでき、記事に載せた14と19の入力では記事どおりの出力になります（出力は韓国語なので訳して示します）。

$ echo 14 | ./greedy2021
10円硬貨1枚、7円硬貨0枚、1円硬貨4枚

問題は入力がおかしいときです。scanf の戻り値を見ていないので、標準入力が空だったり数字でなかったりすると、初期化されていない m のまま計算を始めます。空入力で3回動かすと、10円硬貨の枚数が 1,467,678、4,968,939、4,092,395 と毎回違う値になりました。未初期化のローカル変数を読むのは未定義動作ですが、-Wall -Wextra も AddressSanitizer・UBSan も検出しませんでした。if (scanf("%d", &m) != 1 || m < 0) で先に入力を確かめるべきです。また0円を入れると「解が求められません」と表示されますが、0円は0枚で払えるので、ここも直す点です。

以下が修正した貪欲関数と、同じ金額の最少枚数をDPで求める関数です。1枚ずつ引く代わりに割り算で枚数を一度に出します。

/* coins sorted from largest to smallest */
static int greedy(const int *c, int n, int amount, int used[])
{
    int total = 0;
    for (int i = 0; i < n; i++) {
        used[i] = amount / c[i];
        amount -= used[i] * c[i];
        total += used[i];
    }
    return amount == 0 ? total : -1;          /* -1: cannot pay exactly */
}

/* dp[a] = minimum number of coins for amount a */
static int dp_min(const int *c, int n, int amount)
{
    static int dp[MAXA + 1];
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        dp[a] = INT_MAX;
        for (int i = 0; i < n; i++)
            if (c[i] <= a && dp[a - c[i]] != INT_MAX && dp[a - c[i]] + 1 < dp[a])
                dp[a] = dp[a - c[i]] + 1;
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

お釣り問題：貪欲法が正しい硬貨と外れる硬貨

まず日本の硬貨6種類で1,266円を払うと、貪欲法もDPも8枚で一致しました。

{500,100,50,10,5,1} amount 1266: greedy 8 coins (500x2 100x2 50x1 10x1 5x1 1x1), DP 8 coins

ほかの硬貨体系でも同じ関数に通しました（clang -std=c17 -Wall -Wextra -fsanitize=address,undefined、警告0件）。

{4,3,1}        amount    6: greedy 3 coins (4x1 3x0 1x2), DP 2 coins
{10,7,1}       amount   14: greedy 5 coins (10x1 7x0 1x4), DP 2 coins
{25,10,5,1}    amount   30: greedy 2 coins (25x1 10x0 5x1 1x0), DP 2 coins
{25,15,1}      amount   30: greedy 6 coins (25x1 15x0 1x5), DP 2 coins

{4,3,1}で6を作るとき、貪欲法は4+1+1の3枚、DPは3+3の2枚です。1つの金額だけでは偶然かもしれないので、1から2,000まで全金額で比べました。

{500,100,50,10,5,1}    1..2000: greedy != DP for   0 amounts
{25,10,5,1}            1..2000: greedy != DP for   0 amounts
{4,3,1}                1..2000: greedy != DP for 499 amounts (first: 6)
{10,7,1}               1..2000: greedy != DP for 597 amounts (first: 14)
{25,15,1}              1..2000: greedy != DP for 1185 amounts (first: 30)

ここで2021年の説明を1つ訂正します。当時は「大きい硬貨が小さい硬貨の倍数になっていないと貪欲法は使えない」と書きました。倍数関係があれば貪欲法が最適なのは正しいのですが、倍数であることは必須ではありません。米国の硬貨{25,10,5,1}では25が10の倍数ではないのに、2,000通りすべてで貪欲法が最適でした。このように貪欲法が常に最適になる硬貨体系を「標準的（canonical）な体系」と呼びます。

確認範囲を無限に広げる必要もありません。Kozen と Zaks（1994）の結果によると、貪欲法が外れる金額があるなら、最小の反例はいちばん大きい2枚の硬貨の和より小さいところにあります。上の結果もそのとおりで、{4,3,1}の最初の反例6は4+3=7未満、{10,7,1}の14は17未満、{25,15,1}の30は40未満です。ゲーム内通貨やポイントの単位を自分で決めるなら、その上限までDPと比べれば貪欲法でお釣りを計算してよいかがすぐわかります。

区間スケジューリングと証明のスケッチ

貪欲法が確実に正しい代表例が、区間スケジューリング（activity selection）です。会議室が1つあり、開始・終了時刻の決まった予約がたくさんあるとき、重ならないようにできるだけ多く入れる問題です。2021年の記事にあった区間の図は出典がはっきりしないため削除し、自作の11件の会議（半開区間 [開始, 終了)）で確かめました。3つの並べ替え規則を同じコードで走らせ、2^11 通りの部分集合をすべて調べる全探索で最適値を出しています。

/* sort by a rule, then accept each activity that does not overlap a chosen one */
static int greedy(const Act *src, int n, int (*rule)(const void *, const void *),
                  const char *label)
{
    Act a[16], chosen[16];
    int k = 0;
    for (int i = 0; i < n; i++) a[i] = src[i];
    qsort(a, (size_t)n, sizeof a[0], rule);
    for (int i = 0; i < n; i++) {
        int ok = 1;
        for (int j = 0; j < k; j++)
            if (overlap(&a[i], &chosen[j])) { ok = 0; break; }
        if (ok) chosen[k++] = a[i];
    }
    /* … print chosen[0..k) … */
    return k;
}

11 meetings (optimum by brute force: 4)
  earliest end  : A[1,4) D[5,7) H[8,11) K[12,16)  -> 4
  earliest start: C[0,6) G[6,10) K[12,16)  -> 3
  shortest      : B[3,5) D[5,7) H[8,11) K[12,16)  -> 4
long one starts first (optimum by brute force: 3)
  earliest end  : M[1,3) N[4,6) O[7,9)  -> 3
  earliest start: L[0,10)  -> 1
  shortest      : M[1,3) N[4,6) O[7,9)  -> 3
short one in the middle (optimum by brute force: 2)
  earliest end  : P[0,5) R[6,11)  -> 2
  earliest start: P[0,5) R[6,11)  -> 2
  shortest      : Q[4,7)  -> 1

「開始が早い順」は長い会議が先頭にあると1件で終わり、「短い順」は短い会議が2つの会議にまたがると1件で終わります。3つのケースすべてで最適だったのは「終了が早い順」だけでした。偶然ではないことの証明は短く書けます。

1. 貪欲選択性（交換論法）： いちばん早く終わる会議を g、任意の最適解を O とします。O の中でいちばん早く終わる会議 o を g に入れ替えます。g の終了は o より遅くないので、O の残りの会議（どれも o の終了後に始まる）とも重なりません。件数は同じなので、これも最適解です。つまりg を含む最適解が必ず存在します。
2. 最適部分構造： g を選んだ後に残るのは「g の終了以降に始まる会議からできるだけ多く選ぶ」という、同じ形の小さな問題です。
3. 2つの性質に帰納法を使えば、毎回「終了が最も早い会議」を選ぶ戦略全体が最適になります。実装は終了時刻でソート（O(n log n)）して1回なめるだけで、最後に選んだ会議の終了時刻だけを覚えておけば足ります。上のコードの重なり判定は、ほかの規則と公平に比べるためのものです。

貪欲法を使ってよいかの判断

この証明の2段階が、そのまま一般的な判断基準になります。

• 貪欲選択性： 今いちばん良く見える選択を取っても最適解を逃さないことを、交換論法などで示せるか。硬貨{4,3,1}で6を払う場合、先に4を取ると最適解3+3に届かないので、ここで崩れます。
• 最適部分構造： 選んだ後に残る問題が同じ形の小さな問題で、その最適解を合わせると全体の最適解になるか。お釣り問題はこちらは満たしているので、DPで解けます。
• 証明できないとき： 小さな入力で確かめます。上の2,000金額の比較や 2^11 部分集合の全探索は数十行で書け、一瞬で終わりました。

2021年の記事で「ダイクストラ法、最小全域木、ナップサック問題に貪欲法が使われる」と書いた部分も補足します。ダイクストラ法（辺の重みが非負のとき）と、クラスカル法・プリム法の最小全域木は、貪欲法で最適解が証明されたアルゴリズムです。一方ナップサック問題は、品物を分割できるときだけ貪欲法が最適です。重さ10・20・30、価値60・100・120の品物3つ、容量50で確かめました。

0/1 greedy by ratio: 160, 0/1 optimum: 220, fractional greedy: 240

価値/重さの比が高い順に丸ごと入れると160、実際の最適は重さ20と30の組み合わせで220です。同じ順で最後の品物を切って入れてよければ240になり、分割可能な問題では最適です。分割できない0/1ナップサックはDPで解きます。

まとめ

• 貪欲法は速くて単純ですが、最適解の保証は問題ごとに証明が必要です。
• お釣り問題では、日本の硬貨6種類と米国の硬貨は1〜2,000の全金額で貪欲法が正しく、{4,3,1}・{10,7,1}・{25,15,1}は数百通りで外れました。倍数関係は必須ではありません。
• 反例があるなら大きい2枚の硬貨の和より小さい金額に現れるので、その範囲をDPと比べれば判定できます。
• 区間スケジューリングでは「終了が早い順」だけが最適で、交換論法で証明できます。
• 同じやり方で検証し直した関連記事：ソートアルゴリズム、二分探索、線形探索。