Loading article…
お釣り問題とは、特定の額面の硬貨を何枚組み合わせれば、所定の金額になるかを求める問題です。これは整数ナップサック問題の特殊なケースであり、通貨以外にも幅広い応用があります。
これは、コインお釣り問題の最も一般的な変形でもあります。コインお釣り問題とは、利用可能な無限のコインの額面が与えられたときに、コインの順序を考慮せずに、特定の金額のお釣りを作る可能な方法の数を求める、分割問題の一般的なケースです。
コインの価値は、 w 1からw nまで昇順に並べられたn 個の異なる正の整数値 (整数) のセットでモデル化できます。問題は、正の整数である金額Wが与えられたとき、コインの価値w jが使用される頻度を表す各x jに対して、コインの総数f ( W ) を最小化する非負 (正またはゼロ)整数のセット{ x 1、x 2、 ...、x n } を見つけることです。
対象
変化生成問題の応用例としては、ダーツのゲームで9本のダーツでフィニッシュする方法を計算することが挙げられる。
もう一つの応用例は、質量分析における特定の質量／電荷ピークの原子（または同位体）組成の可能性を計算することである。
古典的な動的計画法戦略では、現在のしきい値に合計されるすべてのより小さな値の組み合わせを見つけることで、上方向に作業を進めます。[ 3 ]したがって、各しきい値では、目標金額Wまで上方向に作業を進めるために、以前のすべてのしきい値が考慮される可能性があります。このため、この動的計画法アプローチでは、O(nW)のステップ数が必要になります。ここで、 nはコインの種類数です。
以下は、部分問題の最適解を追跡するために行列を使用する動的計画法の実装例です（Python 3を使用）。この実装では、最小のコイン数を返します。与えられたコインで釣り銭を作る方法がない場合は、「無限大」を返します。最適解となるコインのセットを取得するために、2つ目の行列を使用することもできます。
def _get_change_making_matrix ( set_of_coins , r : int ): m = [[ 0 for _ in range ( r + 1 )] for _ in range ( len ( set_of_coins ) + 1 )] for i in range ( 1 , r + 1 ): m [ 0 ][ i ] = float ( "inf" ) # デフォルトでは、お釣りを作る方法はありませんreturn mdef change_making ( coins , n : int ): """この関数は、すべてのコインが無限に利用できることを前提としています。 コインを一度だけ使用する場合は、m[c][r - coin] を m[c - 1][r - coin] に変更します。n は、最も少ないコインで取得する数値です。coins は、利用可能な額面のリストまたはタプルです。 """ m = _get_change_making_matrix ( coins , n ) for c , coin in enumerate ( coins , 1 ): for r in range ( 1 , n + 1 ): # コインのみを使用するif coin == r : m [ c ][ r ] = 1 # コインを含めることはできません。# r を作成するための以前のソリューションを使用し、# コインを除外しますelif coin > r : m [ c ][ r ] = m [ c - 1 ][ r ] # コインを使用できます。# 次の解のうちどれが最適かを判断します。# 1. r を作成するための前の解法を使用する (コインを使用しない)。# 2. r - coin を作成するための前の解法を使用する (コインを使用しない) ＋ この 1 枚の追加のコインを使用する。else : m [ c ][ r ] = min ( m [ c - 1 ] [ r ] , 1 + m [ c ][ r - coin ]) return m [ - 1 ][ - 1 ]米国や他の多くの国で使用されているような、現実世界の多くの硬貨システムでは、残りの金額を超えない範囲で最大の額面の硬貨を選択する貪欲アルゴリズムによって最適な結果が得られます。しかし、これは任意の硬貨システムや、現実世界のシステムの一部には当てはまりません。たとえば、かつて（現在は廃止された）インドの硬貨の額面である5、10、20、25パイサを考えると、40パイサを作るには、貪欲アルゴリズムでは3枚の硬貨（25、10、5）を選択しますが、最適な解決策は2枚の硬貨（20、20）です。別の例として、ニッケル硬貨（額面25、10、1）を使わずに40米セントを作ろうとすると、同様の結果が得られます。貪欲アルゴリズムでは7枚の硬貨（25、10、5×1）を選択しますが、最適なのは4枚（4×10）です。コインシステムが「正準」であるとは、貪欲アルゴリズムが常にそのお釣り問題を最適に解決する場合を指します。コインシステムが正準であるかどうかは、多項式時間でテストできます。[ 4 ]
「最適額面問題」[ 5 ]は、全く新しい通貨を設計する人々にとっての問題です。これは、お釣りの平均コスト、つまりお釣りを作るのに必要な平均枚数を最小にするために、硬貨にどの額面を選ぶべきかを問うものです。この問題のバージョンでは、お釣りを作る人は（利用可能な額面の中から）最小限の枚数の硬貨を使用すると想定されています。この問題のバリエーションの1つは、お釣りを作る人が、最小限の枚数以上の硬貨が必要な場合でも、「貪欲アルゴリズム」を使用してお釣りを作ると想定しています。現在のほとんどの通貨は1-2-5シリーズを使用していますが、他の額面のセットでは、より少ない額面の硬貨、またはお釣りを作るのに必要な平均枚数の少ない硬貨、あるいはその両方が必要になります。