Python視頻教程之Python貪心算法實例小結

# -*- coding:utf-8 -*-
def main():
  d = [0.01,0.02,0.05,0.1,0.2,0.5,1.0] # 存儲每種硬幣面值
  d_num = [] # 存儲每種硬幣的數(shù)量
  s = 0
  # 擁有的零錢總和
  temp = raw_input('請輸入每種零錢的數(shù)量：')
  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("數(shù)據(jù)有錯")
    return 0
  s = s - sum
  # 要想用的錢幣數(shù)量最少，那么需要利用所有面值大的錢幣，因此從數(shù)組的面值大的元素開始遍歷
  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動態(tài)的改變，
      print("用了%d個%f元硬幣"%(n, d[i]))
    i -= 1
if __name__ == "__main__":
  main()

# -*- coding:utf-8 -*-
def main():
  s = [12,-4,32,-36,12,6,-6]
  print("定義的數(shù)組為：",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("最大子數(shù)組和為：",s_max)
if __name__ == "__main__":
  main()

# 設汽車加滿油后可行駛n公里，且旅途中有k個加油站
def greedy():
  n = 100
  k = 5
  d = [50,80,39,60,40,32]
  # 表示加油站之間的距離
  num = 0
  # 表示加油次數(shù)
  for i in range(k):
    if d[i] > n:
      print('no solution')
      # 如果距離中得到任何一個數(shù)值大于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()