貪欲法とは、各時点で最も良さそうな選択をその場で選んでいくアルゴリズムです。硬貨の合計金額を最小枚数で支払う問題では、そのつど一番大きい硬貨を選ぶという貪欲法がよく使われます。ただし、使える硬貨の種類によっては、貪欲法の選び方が最小枚数にならないことがあります。