お釣りとして渡す硬貨の枚数を最も少なくする問題を考えます。例えば、620円のお釣りを用意する際、貪欲法では「常にその時点で使える最も高価な硬貨を選ぶ」というルールに従います。まず500円玉を1枚選び、残り120円から100円玉を1枚選び、残り20円から10円玉を2枚選ぶことで、計4枚という最適な組み合わせを素早く見つけることができます。

もう少し詳しく