Python贪心算法实例小结

 # -*- 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 # 要想用的钱币数量最<mark style="color:transparent">来源gaodaimacom搞#代%码网</mark>少，那么需要利用所有面值大的钱币，因此从数组的面值大的元素开始遍历 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 -= 1 if __name__ == "__main__": main() 

 # -*- 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()<pre></div><p><strong>3. </strong>一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。 对于给定的n(n <= 5000)和k(k <= 1000)个加油站位置，编程<strong>计算最少加油次数。</strong></p><div class="gaodaimacode"><pre class="prettyprint linenums"> # 设汽车加满油后可行驶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 = n: # 当局部和大于n时则局部和更新为当前距离 s = d[i] # 贪心意在令每一次加满油之后跑尽可能多的距离 num += 1 i += 1 print(num) if __name__ == '__main__': greedy()