change-making problemは、与えられた金額に加算される（特定の金種の）コインの最小数を見つける問題に対処します。 これは整数ナップザック問題の特別なケースであり、単なる通貨よりも広い用途を持っています。
また、コイン変更問題の最も一般的なバリエーションであり、無限のコインセットの利用可能な金種を考えると、目的は、コインの順序を考慮せずに、特定の金額の変更を行う可能な方法の数を見つけることであるパーティションの一般的なケースである。
変更を行うことは最小化の問題であり、与えられた量のコインを最小限にしなければならない解決策を選択します。
変更を行うことは最小化の問題です。
- 貪欲な方法
2。 Dynamic Method
dynamic programming
古典的な動的計画法は、現在のしきい値に合計されるすべての小さい値の組み合わせを見つけることによって上向きに動作します。したがって、各しきい値では、以前のすべてのしきい値が目標金額Wまで上方に働くと考えられる可能性があります。このため、この動的計画法では、目標金額Wで少なくとも二次であるいくつかのステップが必要になる可能性があります。
最適なコイン変更これを見てきましたが、可能な限り最小のコイン数を使用して、金種のシステムを使用して変更を行いたいと考えています。 時には、貪欲なアルゴリズムが最適解を与えることがあります。 しかし、時にはそうではありません—例は、動的アルゴリズムが15=を与えるシステム（12、5、1）でした12 + 1 + 1 + 1 しかし、より良い答えは15=5 + 5 + 5….. しかし、dynamicは常にその分母内で最適解または可能な最小コインを与えます。
ステップ：-
最小のnoが見つかります。 量のために必要なコインの。
金額は、私たちが変更を行っている金額です。最初にminを設定します。
いいえ。. 必要なコインのすなわち,min=INFINITY
これは、最初に必要なコインの数がわからないことを意味します。
次に、各金種のコインをチェックし、それが解決策を得るために使用できるかどうかを確認します。可能であれば、min変数とcoin変数を更新します。
可能であれば、min変数とcoin変数を更新します。
ここで、min=minimum no. 量の変更を行うために必要なコインの
コイン=ソリューション内のコインの最初のインデックス
例：
量=5
コイン={1,2,3}
変更を行う方法=5
