貪欲アルゴリズムは、最終的なソリューションが全体的な意味で最適であることを期待して、各ステップで最適な (現在のステップ内で) バリアントを選択するアルゴリズムです。
小さな例:
さまざまな額面のコインが無制限にあり、金額 S を集める必要があるとします。2 つの具体的なケースを考えてみましょう。それぞれを貪欲なアルゴリズムで解決しようとします。
つまり、次のように動作します。各ステップで、残額を超えない最高額面のコイン (ステップ内で最良の選択肢) を 1 枚取り出します。
a) 硬貨の額面を 1、5、10 とし、S = 27 とします。
1) テイク 10、S: 27 -> 17
2) テイク 10、S: 17 -> 7
3) テイク 5、S: 7 -> 2
4) テイク 1、S: 2 -> 1
5) テイク 1、S: 1 -> 0
その結果、彼らは5枚のコインを獲得しました。 4 コイン以下では 27 点を獲得できないことを独自に (たとえば総当たりで) 確認できます。
b) コインの額面を 1、5、7 とし、S = 24 とします。
1) テイク 7、S: 24 -> 17
2) テイク 7、S: 17 -> 10
3) テイク 7、S: 10 -> 3
4) テイク 1、S: 3 -> 2
5) テイク 1、S: 2 -> 1
6) テイク 1、S: 1 -> 0.
6枚のコインで得点しましたが、額面7の2枚と額面5の2枚の計4枚のコインでSを獲得できました。
この例からわかるように、貪欲なアルゴリズムで問題を解決できるとは限りません。しかし、全体として最適な答えが得られるのであれば、通常は動的計画法や他の手法を使用するよりも簡単です。