查看: 114|回复: 0

扣丁学堂Python在线教程之Python贪心算法实例小结

发表于 2018-6-27 13:10:51

本篇文章扣丁学堂Python培训小编主要和大家分享一下Python贪心算法实例,文章中结合三个常见实例分析了贪心算法的原理及解决具体问题的相关使用技巧,喜欢Python开发的小伙伴可以随着小编一起来了解下。


本文实例讲述了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))
    s += d * d_num # 计算出收银员拥有多少钱
  sum = float(raw_input("请输入需要找的零钱:"))
  if sum > s:
    # 当输入的总金额比收银员的总金额多时,无法进行找零
    print("数据有错")
    return 0
  s = s - sum
  # 要想用的钱币数量最少,那么需要利用所有面值大的钱币,因此从数组的面值大的元素开始遍历
  i = 6
  while i >= 0:
    if sum >= d:
      n = int(sum / d)
      if n >= d_num:
        n = d_num # 更新n
      sum -= n * d # 贪心的关键步骤,令sum动态的改变,
      print("用了%d个%f元硬币"%(n, d))
    i -= 1
if __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
    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()
以上就是扣丁学堂Python在线教程小编给大家分享的Python贪心算法实例小结,希望对小伙伴们有所帮助,想要了解更多内容的小伙伴可以登录扣丁学堂官网咨询。扣丁学堂是专业的Python培训机构,不仅有专业的老师和与时俱进的课程体系,还有大量的Python在线教程供学员观看学习,想要学习Python的小伙伴快快行动吧。扣丁学堂Python技术交流群:279521237。


文章转载自:扣丁学堂http://www.codingke.com/


回复

使用道具 举报