硬貨の問題とは
A円支払うために必要な硬貨の枚数を最小にする組み合わせを求める問題。
コインの問題、お釣り生成問題（Change-Making Problem : CMP）、とも呼ばれる。
この問題は競技プログラミング等で貪欲法を用いて解かれることが多いですが、貪欲法で最適解が求まることは自明ではありません。
貪欲法で解ける場合
例えば、日本の通貨体系（1円、5円、10円、...）では、価値の大きい硬貨から順に使っていく貪欲法で最適解を求めることができます。
貪欲法で解けない場合
仮に日本の通貨に新しく8円硬貨が追加されたとします。
16円を支払うとき、貪欲法で考えると、10円、5円、1円の3枚の硬貨で支払うことになります。
しかし、明らかにこれは最適ではなく、8円硬貨2枚で支払ったほうが硬貨が少なく済みます。
貪欲法で解ける条件は？
硬貨の問題は整数ナップサック問題の特殊型であり、整数ナップサック問題が貪欲法で解けるための条件がそのまま適用できます。
硬貨の問題に限定した条件は以下のようになります。
硬貨を小さい順に
a_1, a_2, \cdots , a_n
と並べたとき、ある$j$（$1\leq j \leq n-1$）について
a_{j+1}=pa_j-\delta
となる$p$と$\delta$（$0 \leq \delta < a_j$）は一意に定まります（割り算の商と余りの式に近い感じです）。
その$p$と$\delta$に対し、
H(\delta)\leq p-1
が全ての$j$について成り立つことが条件です。
ただし、$H(x)$は$x$円を支払う場合に貪欲法を用いて求めた最小の硬貨の枚数とします。
この証明が気になる方は下の参考文献から論文を辿ってみてください。
適用してみる
まず、$a_{j+1}$が$a_j$で割り切れる場合を考えます（日本の通貨体系では2000円札を除き、これが当てはまります）。
このとき、明らかに$\delta=0$、$H(0)=0$で、$p$は1以上となることから、常に条件が成立します。
次に、硬貨が1円、5円、8円、10円だった場合について確認してみます。
$a_j=8$、$a_{j+1}=10$とすると、$p=2$、$\delta=6$と定まり、
H(\delta)=H(6)=2>1=p-1
と、条件が成立しないことが分かります。
まとめ
「隣り合う硬貨が割り切れる関係なら貪欲法でオッケー」くらいのことを覚えていれば競技プログラミング等でも役に立つのではないでしょうか。
あとは日本の通貨なら貪欲法でオッケー、とか。
ただし、隣り合う硬貨が割り切れる関係でないからといって貪欲法が使えないわけではありません。
例えば2000円札と5000円札は割り切れる関係にはありませんが、上の条件を適用してみると貪欲法でオッケーであることが分かると思います。