Python贪心算法实例小结
本文实例讲述了Python贪心算法。分享给大家供大家参考,具体如下:
1.找零钱问题:假设只有1分、2分、五分、1角、二角、五角、1元的硬币。在超市结账时,如果需要找零钱,收银员希望将最少的硬币数找给顾客。那么,给定需要找的零钱数目,如何求得最少的硬币数呢?
#-*-coding:utf-8-*- defmain(): 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("") foriinrange(0,len(d_num0)): d_num.append(int(d_num0[i])) s+=d[i]*d_num[i]#计算出收银员拥有多少钱 sum=float(raw_input("请输入需要找的零钱:")) ifsum>s: #当输入的总金额比收银员的总金额多时,无法进行找零 print("数据有错") return0 s=s-sum #要想用的钱币数量最少,那么需要利用所有面值大的钱币,因此从数组的面值大的元素开始遍历 i=6 whilei>=0: ifsum>=d[i]: n=int(sum/d[i]) ifn>=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()
2.求最大子数组之和问题:给定一个整数数组(数组元素有负有正),求其连续子数组之和的最大值。
#-*-coding:utf-8-*- defmain(): s=[12,-4,32,-36,12,6,-6] print("定义的数组为:",s) s_max,s_sum=0,0 foriinrange(len(s)): s_sum+=s[i] ifs_sum>=s_max: s_max=s_sum#不断更新迭代s_max的值,尽可能的令其最大 elifs_sum<0: s_sum=0 print("最大子数组和为:",s_max) if__name__=="__main__": main()
3.一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法,指出应在哪些加油站停靠加油,使沿途加油次数最少。对于给定的n(n<=5000)和k(k<=1000)个加油站位置,编程计算最少加油次数。
#设汽车加满油后可行驶n公里,且旅途中有k个加油站 defgreedy(): n=100 k=5 d=[50,80,39,60,40,32] #表示加油站之间的距离 num=0 #表示加油次数 foriinrange(k): ifd[i]>n: print('nosolution') #如果距离中得到任何一个数值大于n则无法计算 return i,s=0,0 #利用s进行迭代 whilei<=k: s+=d[i] ifs>=n: #当局部和大于n时则局部和更新为当前距离 s=d[i] #贪心意在令每一次加满油之后跑尽可能多的距离 num+=1 i+=1 print(num) if__name__=='__main__': greedy()
更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》
希望本文所述对大家Python程序设计有所帮助。