Python贪心算法实例小结

yipeiwu_com6年前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[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 -= 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[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文件与目录操作技巧汇总

希望本文所述对大家Python程序设计有所帮助。

相关文章

python3编码问题汇总

python3编码问题汇总

这两天写了个监测网页的爬虫,作用是跟踪一个网页的变化,但运行了一晚出现了一个问题。。。。希望大家不吝赐教! 我用的是python3,错误在对html response的decode时抛出...

Python实现微信自动好友验证,自动回复,发送群聊链接方法

Python实现微信自动好友验证,自动回复,发送群聊链接方法

引言: 一开始二维码加群,但是呢,这个东西隔一段时间会过期,我需要 每隔一段时间去更新二维码,然后当群人数超过100人了,只能邀请进群, 这个时候就需要别人添加我为好友,然后我通过,打开...

Python3使用requests模块实现显示下载进度的方法详解

本文实例讲述了Python3使用requests模块实现显示下载进度的方法。分享给大家供大家参考,具体如下: 一、配置request 1. 相关资料 请求关键参数:stream=True...

python中ASCII码和字符的转换方法

将ASCII字符转换为对应的数值即‘a'-->65,使用ord函数,ord('a') 反之,使用chr函数,将数值转换为对应的ASCII字符,chr(65) 可以同时使用这两个函数...

spyder常用快捷键(分享)

最近在学习tensorflow框架,在ubuntu下用到python的一个ide --spyder,以下是常用快捷键 Ctrl+1:注释/撤销注释 Ctrl+4/5:块注释/撤销块注释...