贪心算法(又称贪婪算法)是指，在对问题求解时

贪心算法（也称为贪心算法）意味着在解决一个问题时，它总是做出一个当下看起来不错的选择。也就是说，在不考虑整体最优性的情况下，他所做的是某种意义上的局部最优解。

贪心算法不保证最优解，但在某些问题中贪心算法的解是最优解。需要判断一个问题是否可以通过贪心算法来解决。贪心算法与其他算法有明显的区别。动态规划是将问题的所有子问题的解综合起来得到当前最优解（全局最优解），而不是贪心选择；回溯的方法是尝试选择一条路，如果选错了，可以“悔改”，即回去再选择一次。

1 变更问题

假设店主需要找n元，硬币的面额有100元、50元、20元、5元、1元，如何找零才能尽量减少需要的硬币数量？（注：没有10元面额）

找376元找零怎么样？100*3+50*1+20*1+5*1+1*1=375

代码显示如下：

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

2 背包问题

常见的背包问题包括整数背包问题和部分背包问题。问题的描述是这样的。

小偷在商店里找到 n 件物品，第 i 件物品价值 Vi 元，重量为 Wi kg。他想要尽可能高的值，但他的背包最多只能装W公斤。他应该拿走那些货物吗？

例子：

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

显然，贪心算法绝对可以得到分数背包的最优解。我们计算每个物品的单位重量值，然后按降序排列，然后开始取物品。这种类型的物品只要能装满，就可以满载。进去，如果放不下，就部分放进去，直到背包装满为止。

而对于这个问题，显然0-1背包肯定是不满的。即使偶尔发生，也不能满足所有的0-1背包问题。0-1背包（也称为整数背包问题）也可以分为两种：一种是每种类型的物品数量是有界的。一个是无界的，即随心所欲，两者都不能使用贪婪策略。0-1 背包问题是一个典型的第一个整数背包问题。

小数背包代码实现：

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

有n个非负数，以字符串拼接的方式拼接成一个整数。如何连接以最大化结果整数？

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

注1：字符串比较数的大小与整数比较数的大小不同！！！字符串比较的大小是先看第一个数字，越大的越大，但是如何比较长字符串和短字符串呢？例如，128 与 1286 比较

思路如下：

# 简单：当比较两个相等时

a = '96' 
b = '97' 
  
a + b if a > b else b + a 

# 以下不等数比较时，贪心算法怎么用？

# 我们转换想法0 1背包问题回溯算法，拼接字符串，比较结果

 a = '128' 
b = '1286' 
 # 字符串相加 
a + b = '1281286' 
b + a = '1286128' 
  
a + b if a + b > b + a else b + a 

数字拼接代码如下：

4 活动选择题

假设有 n 个活动占用同一个空间0 1背包问题回溯算法，并且该空间一次只能由一个活动使用。

每个活动都有一个开始时间Si和一个结束时间Fi（标题中的时间用整数表示），表示活动占据区间[Si,fi)内的空间。（注：左开右闭）

问：安排哪些活动以最大限度地增加在场地举办的活动数量？

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

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

如果a=b，结论成立

如果a!=b，则b的结束时间一定晚于a的结束时间，则将最优解中的b替换为a，a一定不能与最优解中的其他活动时间重叠，所以替换后也是最优解。

代码显示如下：

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

5 最大子订单和

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

代码显示如下：

def maxSubarray(li): 
 s_max, s_sum = 0, 0 
 for i in range(len(li)): 
 s_sum += li[i] 
 s_max = max(s_max, s_sum) 
 if s_sum < 0: 
 s_sum = 0 
  
 return s_max