一.引言
本文将通过两个问题和两道例题带你入门贪心算法。
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最优（最好或最有利）的选择，从而希望导致全局最优解的算法。贪心算法不保证找到全局最优解，但通常可以快速找到一个接近最优解的解。
二.背包问题和找零问题
1.背包问题
即为给你一个背包的容量，告诉你每个物品的价值和重量，找到最大价值的物品
代码实现：
解析：这不是0/1背包问题，而是分数背包问题（可以拿一部分物品），我们先对goods的单价排序，然后创建一个列表来记录每个物品要拿多少，然后遍历goods，如果背包容量大于物品重量，则记为1，背包容量减少，如果不够则记录分数，依次循环得到数量和价值
结果：
我们看到前面两个拿最多的后，最后一个只能拿三分之二，最终总价值最大。
2.找零问题
已知我们有1,5,20,50,100面额的钞票，给你一个数，用最少的钞票表示出来
结果：
输入376
得到
三.例题
1.数字拼接问题
有n个非负数，将其按照字符串拼接方式拼接成一个整数。如何拼接可以使得整数最大？
先拿两个数比较，把它们转化为字符串，a+b和b+a谁大就谁放前面，然后拼接在一起
代码实现：
from functools import cmp_to_key
li=[32,94,128,1286,6,71]
def xy_cmp(x,y):
if x+y<y+x:
return 1
elif x+y>y+x:
return -1
else:
return 0
def number_join(li):
li=list(map(str,li))
li.sort(key=cmp_to_key(xy_cmp))#python2中支持cmp，但py3只支持key
return "".join(li)#""里面是分隔符，使用join方法将字符串列表连接成一个单独的字符串，分隔符为一个空字符串
print(number_join(li))注意点：1.列表内置的sort不同于python的内置函数sorted，sort在原列表上修改，而sorted会创建一个新迭代对象，不会修改源对象。
2.sort方法只有python2才支持cmp参数，因此在python中想要实现自己的compare必须用到cmp_to_key的方法，最后实现的是降序排列（当然也可以用key加lambda实现）
3.对于compare的返回值
- 如果返回值为负数，表示第一个参数小于第二个参数。
- 如果返回值为零，表示两个参数相等。
- 如果返回值为正数，表示第一个参数大于第二个参数
运行结果
2.活动选择问题
假设有n个活动，这些活动都要占用同一片场地，而场地在某时刻只能供一个活动使用，每个活动都有一个开始时间和结束时间，问安排哪些活动能够使该场地举办的活动个数最多？
代码实现：
activities=[(1,4),(3,5),(0,6),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16),(5,7)]
#保证活动是按照结束时间排好的
activities.sort(key=lambda x:x[1])
def activity_selection(a):
res=[a[0]]
for i in range(1,len(a)):
if a[i][0]>=res[-1][1]: #当前活动的开始时间大于等于结果中最后活动的结束时间
#不冲突
res.append(a[i])
return res
print(activity_selection(activities))运行结果：
文章来源：https://www.toymoban.com/news/detail-807273.html
感谢阅读，如果有帮助，点赞支持！文章来源地址https://www.toymoban.com/news/detail-807273.html
到了这里，关于【Python】贪心算法入门的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
