Python常用的算法——贪心算法（又称贪婪算法），你知道吗？

贪心算法(又称贪婪算法)是指，在对问题求解时，总是做出在当前看来是好的选择。也就是说，不从整体最优上加以考虑，他所做出的的时在某种意义上的局部最优解。

贪心算法并不保证会得到最优解，但是在某些问题上贪心算法的解就是最优解。要会判断一个问题能否用贪心算法来计算。贪心算法和其他算法比较有明显的区别，动态规划每次都是综合所有问题的子问题的解得到当前的最优解(全局最优解)，而不是贪心地选择;回溯法是尝试选择一条路，如果选择错了的话可以“反悔”，也就是回过头来重新选择其他的试试。

1 找零问题

假设商店老板需要找零 n 元钱，钱币的面额有100元，50元，20元，5元，1元，如何找零使得所需钱币的数量最少?(注意：没有10元的面额)

那要是找376元零钱呢? 100*3+50*1+20*1+5*1+1*1=375

代码如下：

1. # t表示商店有的零钱的面额 
2. t = [100, 50, 20, 5, 1] 
3.   
4. # n 表示n元钱 
5. def change(t, n): 
6.  m = [0 for _ in range(len(t))] 
7.  for i, money in enumerate(t): 
8.  m[i] = n // money # 除法向下取整 
9.  n = n % money # 除法取余 
10.  return m, n 
11.   
12. print(change(t, 376)) # ([3, 1, 1, 1, 1], 0) 

2 背包问题

常见的背包问题有整数背包和部分背包问题。那问题的描述大致是这样的。

一个小偷在某个商店发现有 n 个商品，第 i 个商品价值 Vi元，重 Wi 千克。他希望拿走的价值尽量高，但他的背包最多只能容纳W千克的东西。他应该拿走那些商品?

• 0-1背包：对于一个商品，小偷要么把他完整拿走，要么留下。不能只拿走一部分，或把一个商品拿走多次(商品为金条)
• 分数背包：对于一个商品，小偷可以拿走其中任意一部分。(商品为金砂)

举例：

对于 0-1 背包 和 分数背包，贪心算法是否都能得到最优解?为什么?

显然，贪心算法对于分数背包肯定能得到最优解，我们计算每个物品的单位重量的价值，然后将他们降序排序，接着开始拿物品，只要装得下全部的该类物品那么就可以全装进去，如果不能全部装下就装部分进去直到背包装满为止。

而对于此问题来说，显然0-1背包肯定装不满。即使偶然可以，但是也不能满足所有0-1背包问题。0-1背包(又叫整数背包问题)还可以分为两种：一种是每类物品数量都是有限的(bounded)。一种是数量无限(unbounded)，也就是你想要的多少有多少，这两种都不能使用贪心策略。0-1背包是典型的第一种整数背包问题。

分数背包代码实现：

1. # 每个商品元组表示（价格，重量） 
2. goods = [(60, 10), (100, 20), (120, 30)] 
3. # 我们需要对商品首先进行排序，当然这里是排好序的 
4. goods.sort(key=lambda x: x[0]/x[1], reverse=True) 
5.   
6. # w 表示背包的容量 
7. def fractional_backpack(goods, w): 
8.  # m 表示每个商品拿走多少个 
9.  total_v = 0 
10.  m = [0 for _ in range(len(goods))] 
11.  for i, (prize, weight) in enumerate(goods): 
12.  if w >= weight: 
13.  m[i] = 1 
14.  total_v += prize 
15.  w -= weight 
16.  # m[i] = 1 if w>= weight else weight / w 
17.  else: 
18.  m[i] = w / weight 
19.  total_v += m[i]*prize 
20.  w = 0 
21.  break 
22.  return m, total_v 
23.   
24. res1, res2 = fractional_backpack(goods, 50) 
25. print(res1, res2) # [1, 1, 0.6666666666666666] 
26. 1.3 拼接最大数字问题 

有 n 个非负数，将其按照字符串拼接的方式拼接为一个整数。如何拼接可以使得得到的整数最大?

例如：32， 94， 128， 1286， 6， 71 可以拼接成的最大整数为 94716321286128.

注意1：字符串比较数字大小和整数比较数字大小不一样!!! 字符串比较大小就是首先看第一位，大的就大，可是一个字符串长，一个字符串短如何比较呢?比如128和1286比较

思路如下：

# 简单的：当两个等位数相比较

1. a = '96' 
2. b = '97' 
3.   
4. a + b if a > b else b + a 

# 当出现了下面的不等位数相比较，如何使用贪心算法呢?

# 我们转化思路，拼接字符串，比较结果

1.  a = '128' 
2. b = '1286' 
3.  # 字符串相加 
4. a + b = '1281286' 
5. b + a = '1286128' 
6.   
7. a + b if a + b > b + a else b + a 

数字拼接代码如下：

1. from functools import cmp_to_key 
2.   
3. li = [32, 94, 128, 1286, 6, 71] 
4.   
5. def xy_cmp(x, y): 
6.  # 其中1表示x>y，-1,0同理 
7.  if x+y < y+x: 
8.  return 1 
9.  elif x+y > y+x: 
10.  return -1 
11.  else: 
12.  return 0 
13.   
14. def number_join(li): 
15.  li = list(map(str, li)) 
16.  li.sort(key=cmp_to_key(xy_cmp)) 
17.  return "".join(li) 
18.   
19. print(number_join(li)) # 94716321286128 

4 活动选择问题

假设有 n 个活动，这些活动要占用同一片场地，而场地在某时刻只能供一个活动使用。

每一个活动都有一个开始时间 Si 和结束时间 Fi (题目中时间以整数表示)表示活动在 [Si, fi) 区间占用场地。(注意：左开右闭)

问：安排哪些活动能够使该场地举办的活动的个数最多?

贪心结论：最先结束的活动一定是最优解的一部分。

证明：假设 a 是所有活动中最先结束的活动，b是最优解中最先结束的活动。

如果 a=b，结论成立

如果 a!=b，则 b 的结束时间一定晚于 a 的结束时间，则此时用 a 替换掉最优解中的 b ，a 一定不与最优解中的其他活动时间重叠，因此替换后的解也是最优解。

代码如下：

1. # 一个元组表示一个活动，（开始时间，结束时间） 
2. activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), 
3.  (8, 12), (2, 14), (12, 16)] 
4.   
5. # 保证活动是按照结束时间排好序,我们可以自己先排序 
6. activities.sort(key=lambda x:x[1]) 
7.   
8. def activity_selection(a): 
9.  # 首先a[0] 肯定是最早结束的 
10.  res = [a[0]] 
11.  for i in range(1, len(a)): 
12.  if a[i][0] >= res[-1][1]: # 当前活动的开始时间小于等于最后一个入选活动的结束时间 
13.  # 不冲突 
14.  res.append(a[i]) 
15.  return res 
16.   
17. res = activity_selection(activities) 
18. print(res) 

5 最大子序和

求最大子数组之和的问题就是给定一个整数数组(数组元素有负有正)，求其连续子数组之和的最大值。下面使用贪心算法逐个遍历。