本文實例講述了Python貪心算法。分享給大家供大家參考，具體如下：

1. 找零錢問題：假設只有 1 分、 2 分、五分、 1 角、二角、 五角、 1元的硬幣。在超市結賬 時，如果 需要找零錢， 收銀員希望將最少的硬幣數找給顧客。那么，給定 需要找的零錢數目，如何求得最少的硬幣數呢？

# -*- coding:utf-8 -*-def main():  d = [0.01,0.02,0.05,0.1,0.2,0.5,1.0] # 存儲每種硬幣面值  d_num = [] # 存儲每種硬幣的數量  s = 0  # 擁有的零錢總和  temp = raw_input('請輸入每種零錢的數量：')  d_num0 = temp.split(" ")  for i in range(0, len(d_num0)):    d_num.append(int(d_num0[i]))    s += d[i] * d_num[i] # 計算出收銀員擁有多少錢  sum = float(raw_input("請輸入需要找的零錢:"))  if sum > s:    # 當輸入的總金額比收銀員的總金額多時，無法進行找零    print("數據有錯")    return 0  s = s - sum  # 要想用的錢幣數量最少，那么需要利用所有面值大的錢幣，因此從數組的面值大的元素開始遍歷  i = 6  while i >= 0:     if sum >= d[i]:      n = int(sum / d[i])      if n >= d_num[i]:        n = d_num[i] # 更新n      sum -= n * d[i] # 貪心的關鍵步驟，令sum動態的改變，      print("用了%d個%f元硬幣"%(n, d[i]))    i -= 1if __name__ == "__main__":  main()

2. 求最大子數組之和問題：給定一個整數數組（數組元素有負有正），求其連續子數組之和的最大值。

# -*- coding:utf-8 -*-def main():  s = [12,-4,32,-36,12,6,-6]  print("定義的數組為：",s)  s_max, s_sum = 0, 0  for i in range(len(s)):    s_sum += s[i]    if s_sum >= s_max:      s_max = s_sum # 不斷更新迭代s_max的值，盡可能的令其最大    elif s_sum < 0:      s_sum = 0  print("最大子數組和為：",s_max)if __name__ == "__main__":  main()

3. 一輛汽車加滿油后可行駛n公里。旅途中有若干個加油站。設計一個有效算法，指出應在哪些加油站停靠加油，使沿途加油次數最少。 對于給定的n(n <= 5000)和k(k <= 1000)個加油站位置，編程計算最少加油次數。

# 設汽車加滿油后可行駛n公里，且旅途中有k個加油站def greedy():  n = 100  k = 5  d = [50,80,39,60,40,32]  # 表示加油站之間的距離  num = 0  # 表示加油次數  for i in range(k):    if d[i] > n:      print('no solution')      # 如果距離中得到任何一個數值大于n 則無法計算      return   i, s = 0, 0  # 利用s進行迭代  while i <= k:    s += d[i]    if s >= n:      # 當局部和大于n時則局部和更新為當前距離      s = d[i]      # 貪心意在令每一次加滿油之后跑盡可能多的距離      num += 1    i += 1  print(num)if __name__ == '__main__':  greedy()

更多關于Python相關內容感興趣的讀者可查看本站專題：《Python數據結構與算法教程》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》、《Python入門與進階經典教程》及《Python文件與目錄操作技巧匯總》