Greedy Algorithm

グリディアルゴリズムは最も簡単で、最も強力な問題解決方法である.グリディという言葉の意味のように、単純に無知で貪欲に問題を解決するアルゴリズムです.つまり、今の状況では、今は良いものを選ぶしかありません.グリディアルゴリズムは現在の状況のみを考慮し,現在の選択が将来に及ぼす影響は全く考慮しない.グリディアルゴリズムは、事前に暗記する必要がなくて済む可能性の高い問題タイプです.これは,グレディアルゴリズムの意味を知らなくても,容易に思いつき,それに近づくことができることを意味する.しかし,GRADYアルゴリズムを適用できる問題のタイプは多くあるため,多くのタイプの問題に接触,解答,練習する必要がある.
グリディアルゴリズムを最も理解しやすい典型的な例は「お金を探す」問題だ.
カウンターにはお釣りに使える500元、100元、50元、10元のコインが無限に存在すると仮定します.お客様に渡すお金がN元の場合、お探しのコインの最低個数です.しかし、探しているお金Nはいつも10の倍数です.
この問題はグレディのアルゴリズムが分からなくても、簡単に解決できます.コアは最大の通貨単位からお金を探すことです.入力したNが1260元であれば、以下の手順で解決できます.

まず最大の通貨単位500元を探します.
(500円玉2個)

次は

で、いくらでも探せます.
(100円玉2個)

次は

で、いくらでも探せます.
(50元硬貨1枚)

最後の通貨単位は10元で、いくら探してもいいです.
(10元硬貨1枚)

最終的にお客様が受け取ったコインは最低6枚です.この内容を次のようにコード化します.最終的にお客様が受け取ったコインは最低6枚です.この内容を次のようにコード化します.

n = 1260
count = 0

coint_types = [500, 100, 50, 10]

for coin in coin_types :
	count += n // coin
    n %= coin
    
print(count)

グリディアルゴリズムはすべてのアルゴリズム問題に適用されるわけではない.ほとんどの問題にGredyアルゴリズムを適用すると,最適解が見つからない可能性が高い.したがって,グリディアルゴリズムを用いてソリューションを探す場合,そのソリューションが正しいかどうかを確認する必要がある.上記のおつり問題では、大きな通貨単位は小さな通貨単位の倍数であるため、グリディアルゴリズムを用いて問題を解決することができる.800元を探すなら、通貨単位は500元、400元で、100元はどうなりますか?グリディアルゴリズムを採用すれば、全部で4つのコイン(500元+100元+100元+100元+100元)を探し、最適な年は2つのコイン(400元+400元)を探すことです.すなわち,グリディアルゴリズムは必ずしも最適解を見つけることができないため,解法の妥当性を検証する必要がある.
出典:これは就職のためのコードテストで、Python、羅東彬知音で