Python贪心算法实例小结_Python

Python贪心算法实例小结

2021-02-04 00:20wangbowj123 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[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()