本文实例讲述了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程序设计有所帮助。
Python,贪心算法
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线
暴雪近日发布了《魔兽世界》10.2.6 更新内容，新游玩模式《强袭风暴》即将于3月21 日在亚服上线，届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。
艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒 经典版》的玩家都可以获得奖励。