両替問題：貪欲法と最適解

硬貨の組と金額を入力してください。このページでは、二通りの方法でその金額を支払います。一つは、使える硬貨のうち最大のものを、残額がなくなるか使える硬貨がなくなるまで選ぶ貪欲法。もう一つは、0から入力額まで表を埋めて求める、硬貨の枚数が最小となる方法です。表の下には、指定した範囲内の各金額について、貪欲法で必要以上の枚数を使う箇所が示されます。

計算例 — 両替問題：貪欲法と最適解

貪欲法が余分に使う枚数	1
1から240までで貪欲法が最適でない金額	240件中42件
1から240までで貪欲法が余分に使う最大枚数	1
コーゼンとザックスの上界：最大の二額面の和	54
貪欲法が初めて最適解を逃す金額	48

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

レッスン

理論 — 両替問題：貪欲法と最適解

両替問題とは、各額面の硬貨を何枚でも使えるとき、指定された金額になる組合せのうち枚数が最少のものを求める問題です。貪欲法は、使える最大の硬貨を選ぶ操作を繰り返します。動的計画法では、まず小さい金額をすべて解くことで厳密な最適解を求めます。すなわち、M(0) = 0およびM(a) = 1 + min M(a − c)です。後者ではc ≤ aを満たす硬貨cについて最小値を取ります。すべての金額で貪欲法が最適となる硬貨体系を正準硬貨体系と呼びます。

各記号の意味

M(a): 金額aを支払う最少枚数。表のマスaに入る数
G(a): 金額aに対して貪欲法が使う硬貨の枚数
cₘ, cₘ₋₁: 最大と二番目の額面。貪欲法が初めて最適解を逃す金額が存在するなら、その和より小さい

前提: 各額面の硬貨を無制限に使え、額面は整数、費用として数えるのは硬貨の枚数だけとします。レジのフローリンが品切れなら、別の問題です。上界を使うには額面1が必要です。これがなければ支払えない金額が生じ、表では支払える金額でも貪欲法が途中で行き詰まることがあります。

旧イギリス通貨では四シリングで貪欲法が破れる 🖖

1971年以前の英国を押してください。四シリング、すなわち48dを支払うとします。貪欲法は、まず使える最大のハーフクラウン（30d）、次にシリング（12d）、六ペンス硬貨（6d）を選び、計三枚になります。24dのフローリンなら二枚で同じ48dです。以後、貪欲法は30ペンスごとに六つの金額、48–53d、78–83dと続いて228–233dまで、最適解を逃します。一ポンドに含まれる240件のうち42件です。余分なのは毎回ちょうど一枚なので、帯グラフの赤い棒はすべて同じ高さになります。この六つは、一枚以上のハーフクラウンを選んだあと18から23ペンスが残る金額です。ハーフクラウンを一枚戻し、48dの部分をフローリン二枚に替えれば、硬貨を一枚減らせます。半ペニーを加えても解決しません。半ペニー単位で1, 2, 6, 12, 24, 48, 60と入力し、480まで調べてください。最初の反例は96半ペンスで、やはり48dです。480件のうち84件で貪欲法が最適解を逃します。先ほどの42件と、それぞれの半ペニー上の金額です。

ハーフクラウンを除けば貪欲法は常に最適 🖖

ハーフクラウンなしを押してください。同じ体系から一種類を除いた1、3、6、12、24ペンスでは、帯グラフが空になります。240件のどこにも反例はありません。どの額面も次の額面を割り切ります。このような連鎖では、ある硬貨を上位の一枚分だけ集めても、その一枚に交換できるため、貪欲法は最適解を逃しません。ハーフクラウンがこの連鎖を崩します。三十は二十四の倍数ではありません。フローリン二枚は、ハーフクラウン一枚に18dを足した額で、その18dにはシリングと六ペンス硬貨が必要です。最初の帯に現れる反例は、すべてこの交換から生じます。硬貨を追加するだけでも直りません。五シリングのクラウンを戻すには、1, 3, 6, 12, 24, 30, 60と入力します。反例は42件から24件に減りますが、最初はなお48dです。クラウンより小さい金額には、クラウンを使えないからです。

硬貨体系の判定は有限回で済む 🖖

48dで貪欲法が破れても、それだけでは4,800dでの結果はわかりません。あらゆる金額について体系を判定するのが、デクスター・コーゼンとシュムエル・ザックスが1994年に発表した定理です。額面1を含む体系で貪欲法が最適解を逃すなら、その最小の金額はc₃ + 1とc_m + c_m−1の間にあります。ここでc₃は小さい方から三番目の額面、c_mとc_m−1は最大と二番目の額面です。米セントを押してください。最大の二額面は100と50で、150未満に反例はありません。この有限範囲の検査だけで、すべての金額が判定できます。ユーロでは300までです。この上界はさらに狭められません。1、3、4を押してください。5と7の間にある金額は6だけで、まさにそこで貪欲法が破れます。帯グラフの破線が上界です。額面1を含む限り、最初の赤い棒は必ずその左側に現れます。

全プロセスの詳細解説

1と5に加える第三の額面は？ 3 ステップ
ある国には額面1と5の硬貨があり、6から30までのどれかを第三の額面dにしようとしています。どのdなら、貪欲法による釣り銭が常に最適になるでしょうか。このページで一度に試せる体系は一つですが、三種類の硬貨に対するコーゼンとザックスの判定法なら、25通りをまとめて解けます。まず1、3、4を押し、すでに検査済みの体系で判定法を試しましょう。

この問題をツールで開く
1. 額面が1 < c < dのとき、d = qc + r、0 ≤ r < cと書きます。どこかに反例があるための必要十分条件は、0 < r < c − qです。1、3、4では、d = 4 = 1 × 3 + 1なので、q = 1、r = 1となり、0 < 1 < 2が成り立ちます。したがって反例があり、ページでは最初の反例として6が見つかります。
  
  $4 = 1 \times 3 + 1 : q = 1, r = 1, 0 < 1 < 3 - 1 = 2$
2. 今度はc = 5です。したがってd = 5q + rで、判定条件は0 < r < 5 − qとなります。qが大きくなるほど、rの入れる範囲は狭くなります。
  
  $d = 5 q + r, 0 \leq r < 5 : 0 < r < 5 - q$
3. q = 1（dは6から9）では、rは1、2、3を取れるため、d = 6、7、8が反例を生みます。q = 2（10から14）ではr = 1または2なので、11と12です。q = 3（15から19）ではr = 1だけで、16になります。q = 4以降は5 − qが1以下となり、条件を満たすrはありません。
  
  $q = 1 : d \in {6, 7, 8} q = 2 : d \in {11, 12} q = 3 : d = 16 q \geq 4 : 5 - q \leq 1$
解答

反例を生むのは6、7、8、11、12、16の六つです。残る十九個はすべて正準で、17から30までのdはどれも含まれます。六つのうち一つを確かめるには、1, 5, 12と入力してください。貪欲法は15を12 + 1 + 1 + 1の四枚で支払いますが、額面5なら三枚で足ります。

$d \in {6, 7, 8, 11, 12, 16} 15 = 12 + 1 + 1 + 1 = 5 + 5 + 5$

学習の道すじ

アルゴリズムが正しい理由

参考文献 (3)

The bound the page draws as a dashed line and settles every system with: if greedy is ever beaten, the smallest amount where it is beaten lies strictly between c₃ + 1 and cₘ + cₘ₋₁; the three-coin rule the worked problem uses; the {1, 3, 4} example and the US system 1, 5, 10, 25, 50, 100 as canonical: D. Kozen and S. Zaks, "Optimal bounds for the change-making problem." Theoretical Computer Science 123(2), 1994, pp. 377-388. DOI 10.1016/0304-3975(94)90134-1
The pre-decimal coins and their values in pence (threepence, sixpence, shilling of 12d, florin of two shillings, half-crown of two shillings and sixpence, crown of five shillings), and the halfpenny's end as legal tender on 31 July 1969: Wikipedia contributors, "£sd", Wikipedia, The Free Encyclopedia, accessed 3 October 2026.
Which coins made up the circulating set at the end, as the Royal Mint itself issued them in 1970: half-crown, florin, shilling, sixpence, threepence, penny and halfpenny: The Royal Mint, "1970 Pre-Decimal UK Proof Set", product description, accessed 3 October 2026.

42Math チーム · 公表された資料と照合しています。訂正のご指摘を歓迎します。