1. 序章

このチュートリアルでは、欲張りアルゴリズムを学習して、指定された金額を変更するためのコインの最小数を見つけます。 通常、この問題は変更の問題と呼ばれます。

最初に、実際の例を使用して変更を行う問題を定義します。 次に、変更を加える問題に対するソリューションアプローチの基本的な考え方を理解し、問題の例を解決することによってその動作を説明します。

次に、欲張りアルゴリズムの擬似コードについて説明し、その時間計算量を分析します。 最後に、説明したアルゴリズムの制限を指摘し、それを克服するための代替案を提案します。

2. 変更作成の問題

変更を行う問題では、配列 =の個別のコイン金種、が提供され、各金種には無限の供給があります。 配列がa 最小数のコインを持ち、合計すると所定の金額になる必要があります。実行可能なソリューション。

変化をもたらす問題をよりよく理解するために、実際の例を考えてみましょう。

私たちが現金カウンターで働いていて、価値のあるコインが無限に供給されていると仮定しましょう。 ここで、最小数のコインを使用した金額を顧客の1人に返却する必要があります。

3. ソリューションアプローチ

欲張りアルゴリズムは、変更を行う問題に対する実行可能な解決策を繰り返し見つけます。

各反復で、は、のように、 say 、の最大額のコインを選択します。 次に、は、ソリューションアレイおよびに金種を追加し続け、をだけ減らします。 である限り。 このプロセスは、ゼロになるまで繰り返されます。

上記の例を解いて、ソリューションのアプローチを理解してみましょう。 以下の画像は、問題の段階的な解決策を示しています。

したがって、金額を変更するには最低4枚のコインが必要であり、その金種はです。

4. 擬似コード

ソリューションアプローチの基本的な考え方がわかったので、アルゴリズムの疑似コードを見てみましょう。

まず、コインの種類の配列を値の昇順で並べ替えます。

次に、配列の最後のインデックスから開始し、最初のインデックスまで繰り返します。 各反復で、各金種のコインをソリューションアレイにできるだけ多く追加し、追加された各コインの金種ごとにデクリメントします。

ゼロになると、反復を停止し、結果としてソリューション配列を返します。

上記のアルゴリズムの時間計算量を分析してみましょう。

コインの種類の配列を（）時間で並べ替えることができます。 同様に、forループには（）時間がかかります。最悪の場合、変更を行うためにコインが必要になる場合があります。

したがって、欲張りアルゴリズムの全体的な時間計算量は（）sinceになります。 ただし、このアプローチは（）時間で効率的に実装できます。

5. 制限

欲張りアルゴリズムの制限は、一部の金種に最適なソリューションを提供しない可能性があることです。

たとえば、上記のアルゴリズムでは、との最適解を取得できません。 特に、それは4つのコインで解決策を提供します。

ただし、上記の問題の最適な解決策は3枚のコインです。

その理由は、欲張りアルゴリズムが段階的にソリューションを構築するためです。 各ステップで、グローバルに最適なソリューションを見つけることを見越して、ローカルに最適な選択肢を選択します。 その結果、欲張りアルゴリズムは局所的な最適値をトラップすることがあり、したがってグローバルに最適なソリューションを提供できませんでした。

別の方法として、動的計画法アプローチを使用して、一般的な入力の最適なソリューションを確認することもできます。 実際、動的計画法ベースのアルゴリズムについては、他の記事で説明します。

6. 結論

この記事では、与えられた金額を変更するためのコインの最小数を見つけるための欲張りアルゴリズムを研究し、その時間計算量を分析しました。 さらに、実際の例を使用して、説明したアルゴリズムの動作を示し、その制限についても説明しました。