问题：

以人民币的硬币为例，假设硬币数量足够多。要求将一定数额的钱兑换成硬币。要求兑换硬币数量最少。

思路说明：

这是用贪婪算法的典型应用。在本例中用python来实现，主要思想是将货币金额除以某硬币单位，然后去整数，即为该硬币的个数；余数则做为向下循环计算的货币金额。 这个算法的问题在于，得出来的结果不一定是最有结果。比如，硬币单位是[1,4,6],如果将8兑换成硬币，按照硬币数量最少原则，应该兑换成为两个4（单位）的硬币，但是，按照本算法，得到的结果是一个6单位和两个1单位的硬币。这也是本算法的局限所在。所谓贪婪算法，本质就是只要找出一个结果，不考虑以后会怎么样。

解决(Python)

  1.   1. #!/usr/bin/env python
  2.     2. #coding:utf-8
  3.     3.   4.   5. def change_coin(money):
  4.     6.     coin = [1,2,5,10,20,50,100]     #1分，2分，5分，1角，2角，5角，1元
  5.     7.     coin.sort(reverse=True)
  6.     8.     money = money*100               #以分为单位进行计算
  7.     9.     change = {}
  8.     10.   11.     for one in coin:
  9.     12.         num_coin = money//one       #除法，取整，得到该单位硬币的个数
  10.     13.         if num_coin>0:
  11.     14.             change[one]=num_coin
  12.     15.         num_remain = money%one      #取余数，得到剩下的钱数
  13.     16.         if num_remain==0:
  14.     17.             break
  15.     18.         else:
  16.     19.             money = num_remain
  17.     20.     return change 
  18.     21.   22. if __name__=="__main__":
  19.     23.     money = 3.42
  20.     24.     num_coin = change_coin(money)
  21.     25.     result = [(key,num_coin[key]) for key in sorted(num_coin.keys())]
  22.     26.     print "You have %s RMB"%money
  23.     27.     print "I had to change you:"
  24.     28.     print "    Coin    Number"
  25.     29.     for i in result:
  26.     30.         if i[0]==100:
  27.     31.             print "Yuan    %d    %d"%(i[0]/100,i[1])
  28.     32.         elif i[0]<10:
  29.     33.             print "Fen    %d    %d"%(i[0],i[1])
  30.     34.         else:
  31.     35.             print "Jiao    %d    %d"%(i[0]/10,i[1])
  32.     36.   37. #执行结果
  33.     38. #You have 3.42 RMB
  34.     39. #I had to change you:
  35.     40. #    Coin    Number
  36.     41. #    Fen    2    1
  37.     42. #    Jiao    2    2
  38.     43. #    Yuan    1    3

解决2(Python)

以下方法，以动态方式，提供最小的硬币数量。避免了贪婪方法的问题。

  1.   1. def coinChange(centsNeeded, coinValues):
  2.     2.     minCoins = [[0 for j in range(centsNeeded + 1)] for i in range(len(coinValues))]
  3.     3.     minCoins[0] = range(centsNeeded + 1)
  4.     4.   5.     for i in range(1,len(coinValues)):
  5.     6.         for j in range(0, centsNeeded + 1):
  6.     7.             if j < coinValues[i]:
  7.     8.                 minCoins[i][j] = minCoins[i-1][j]
  8.     9.             else:
  9.     10.                 minCoins[i][j] = min(minCoins[i-1][j], 1 + minCoins[i][j-coinValues[i]])
  10.     11.     return minCoins[-1][-1]

整理人：豆包AI助手