一、引言：

---

       在我們學習了算法之后，我們一定遇到過貪心算法。而在貪心算法中就有著這樣一個經典的例子——湊錢。

Eg：

        你有面額為10、5、1的紙幣，當你買菜時需要花費26元，請問需要最少的紙幣張數是多少。

        當我們用貪心算法去解決這個問題的時候，我們很簡單的就得到了這樣一個答案：10元兩張、5元一張、1元一張。這里我們來回顧下是怎么得到的——按照貪心的思想，我們要先用面額最大的紙幣來湊，這樣我們就得到了26-2*10=6；得到剩余需要的錢后再接著用面額最大的來湊，最后的結果為：

26-10*2=6；——2張

6-5=1；——1張

1-1=0；——1張

所以總共花了4張紙幣。

        但是當我們遇到些特殊的例子呢？

Eg：你有11、5、1三種面額的紙幣，當你買菜花費了15元，你該如何支付使得花費的紙幣張數最少呢？ 

        上述這個例子如果我們用貪心的思想去做的話得到的結果如下：

15-11=4；——1張

4-1*4=0；——4張

所以總共花費了五張； 

<