コイン両替問題
おつりを渡すレジ係は、金額以下で最大のコインを取り、次のコインを取ります。ユーロやドルなら、これで必ず最少枚数になります。ところがコインを 1、3、4 に変えると、同じやり方では2枚で済む 6 を3枚で払ってしまいます。動的計画法なら、どんなコインでも本当の最小値を求められます。
2つの問い
コイン両替問題には2つの種類があります。1つ目は、ちょうどの金額を作る最少のコイン枚数を求めるもので、釣り銭問題とも呼ばれます。2つ目は、その金額を作るコインの組み合わせが何通りあるかを求めるものです。どちらでも各種類のコインは何枚でも使え、どちらもより小さい金額の答えからすべての金額の答えを組み立てて解きます。
最少枚数をステップごとに
0 から目標までの金額に対応するセルを一列に並べます。金額 0 はコイン 0 枚、それ以外の金額は無限大から始めます。金額を順にたどり、それぞれでその金額以下のコイン c をすべて試します。金額から c を引いたセルにコイン1枚を足したものが候補です。最も小さいものを残します。各セルは左側の、すでに確定したセルだけに依存するので、1回たどるだけで列が埋まります。
例
コインが 1、3、4 のとき、金額 1 は 1 枚、2 は 2 枚、3 は 1 枚(3 が1枚)、4 は 1 枚です。5 では、1(4 は 1 枚なので 2 枚)、3(2 は 2 枚なので 3 枚)、4(1 は 1 枚なので 2 枚)を試し、最良は 2 枚です。6 では、1(5 は 2 枚なので 3 枚)、3(3 は 1 枚なので 2 枚)、4(2 は 2 枚なので 3 枚)を試し、最良は 3 + 3 の 2 枚です。貪欲法なら 4 + 1 + 1 で払っていたところです。
作り方を数える
組み合わせを数えるには、コインを1種類ずつ追加します。最初のコインだけなら、各金額は1通りで作れるか、まったく作れないかです。新しいコイン c が加わると、金額 a を作る方法は、c を使わない以前の方法に、c を再び使ってよいとして a − c を作る方法を足したものになります。後者のそれぞれに c をもう1枚加えると a の作り方になるからです。コインが 1、2、5 のとき、5 を作る方法は 4 通りあります:5、2 + 2 + 1、2 + 1 + 1 + 1、1 + 1 + 1 + 1 + 1。
貪欲法で十分なとき
貪欲法が常に最少枚数を与えるコイン体系を、正準(カノニカル)なコイン体系と呼びます。現代の通貨の多くはそのように設計されており、1994年にデビッド・ピアソンは、コインの種類数に対して多項式的にしか増えないステップ数でコイン体系を判定する方法を示しました。昔のイギリスの硬貨は正準ではありませんでした。貪欲法は 48 ペンスをハーフクラウン、シリング、6ペンス硬貨で払いますが、フロリン2枚で済みます。
試してみよう
アプリを開いて「表」表示に切り替え、「ステップ」を押してください。「最少枚数」モードでは、オレンジのセルが計算中の金額、青のセルがコインを使った残りの小さい金額です。下の行には最後のコインが記録され、最後にこの行をたどってコインを読み取ります。「組み合わせの数」に切り替えると、コインが加わるたびに数が1行ずつ増えていく様子が見られます。
よくある質問
コイン両替問題はナップサック問題ですか?
近い親戚です。最少枚数の問題は個数制限なしナップサック問題の一種で、各コインは額面を重さとする品物であり、ナップサックをちょうど満たし、品物の数を最小にすることが目標です。
時間計算量はどれくらいですか?
k 種類のコインと金額 A に対して、どちらの問題も O(k·A) です。最少枚数の表は A + 1 個のセル、作り方の表は (k + 1)·(A + 1) 個のセルを持ちますが、セルをその場で更新すれば1行で足ります。
なぜコインを決まった順番で数えるのですか?
各金額ですべてのコインを試すと、1 + 2 と 2 + 1 が2通りと数えられてしまいます。コインを1行ずつ追加すれば、組み合わせは常に前のコインから先に作られるので、それぞれがちょうど1回だけ数えられます。
組み合わせの数でもコインを読み取れますか?
1つの答えとしては読み取れません。作り方がたくさんあるからです。最少枚数の問題では各金額の最後のコインを記録しているので、最良の組み合わせを1つ復元するにはそれで十分です。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
コイン両替を試す