【Python】贪心算法入门

一.引言

本文将通过两个问题和两道例题带你入门贪心算法。

贪心算法（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))

运行结果：