贪心算法
定义
是指在对问题求解时，总是做出当前看来是最好的选择，着眼于眼前（做出目前对自己好的：贪心），不从整体最优上考虑，做出某种意义上的局部最优解。但有时贪心算法的解就是最优解。要会判断一个问题是否用贪心算法来计算。
例题
- 找零问题：假设商店老板需要找零n元钱，钱币的面额有：100元、50元、20元、5元、1元，如何找零使得所需钱币的数量最少？
- 代码求解
li = [i for i in map(int,input().split())]
money = int(input())
def pay_money(li,money):
m = [0 for _ in range(len(li))]
li = sorted(li,reverse=True)
for index,val in enumerate(li):
m[index] = money//val
money = money % val
return m,money
print(pay_money(li,money))
背包问题
0-1背包
有时需要判断0-1背包是否能用贪心算法来做：有时局部的最优解没能装满背包，且导致不是整体最优解
分数背包
对于分数背包而言，使用贪心算法来做一定是整体最优解：背包一定是满的，一点都不剩
举例
一个小偷在某个商店发现有n个商品，第i个商品价值vi元，重wi千克。他希望拿走的价值尽量高，但他的背包最多只能容纳W千克的东西。他应该拿走哪些商品？
-
贪心算法：找到当前的最优解：每个单位商品的价值：商品1、2、3的价值分别为6，5，4
-
0-1背包：对于一个商品，小偷要么把它完整拿走，要么留下。不能只拿走一部分，或把一个商品拿走多次。（商品为金条）
因此，若用贪心算法求解，0-1背包只能拿贪心算法中价值最大的前两个，即商品1和商品2，共计160元，30千克，背包容量为50，50-30<30，不能再拿商品3。而不使用贪心算法，拿商品2和商品3，共计220元，50千克，该决策优于贪心算法决策。
-
分数背包：对于一个商品，小偷可以拿走其中任意一部分。（商品为金沙）
无论是否使用贪心算法，都能使得决策为最优解（该例子分数背包在使用贪心算法下，可拿10千克商品1，20千克商品2和20千克商品3，共计240元）
# 分数背包问题贪心算法求解 goods = [(60,10),(100,20),(120,30)] # 每个商品对应的价值即重量 W = 50 # 背包容量 goods.sort(key=lambda x: x[0] / x[1], reverse=True) # 贪心算法思想（对当前每个商品的价值进行排序，从大到小排序） def fractional_package(goods,W): m = [0 for _ in range(len(goods))] # 用于存放对应每个商品（从大价值到小价值）拿走的数量 total_price = 0 # 用于存放拿走的价值总数 for index,(price, weight) in enumerate(goods): if W >= weight: # 如果当前背包容量大于或等于大价值的重量时，可都拿走 m[index] = 1 # 1代表都拿走 total_price += price W -= weight # 背包总量要改变 else: # 当前背包容量小于大价值的重量时，拿走部分 m[index] = W/weight # 表示拿走商品总重量的几分之几 total_price += m[index] * price W = 0 # 当前无背包空间 break return total_price,m print(fractional_package(goods,W))
拼接最大数字问题
- 题目
-
思想：比首位，首位大的先排，当首位一样，比下一位，以此类推，当都一样只是长度不同，则两数相加进行比较，如何大的数进行存放（两数已排好序）
-
代码实现***（待搞懂cmp_to_key用法）
li = [32,94,128,1286,6,71]
from functools import cmp_to_key
def num_cmp(x,y): # 自定义排序规则
if x + y > y + x:
return 1
elif x + y < y + x:
return -1 # 当返回一个负数时，改变原本的排序顺序（由后往前进行比较，插入）
else:
return 0
def num_join(li):
li = list(map(str,li))
li.sort(key=cmp_to_key(num_cmp),reverse=True)
return li
print("".join(num_join(li)))
活动选择问题
-
题目
-
思想：贪心算法结论：最早结束的活动一定是最优解的一部分。最早结束的先举办。结束时间与开始时间不相撞
-
代码实现
activities = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)]
def activity_choose(li):
li.sort(key=lambda x:x[1]) # 以结束时间为比较对象，按最先结束的先安排为原则进行活动安排
activities_final_choose = [li[0]] # 最先结束一定存在在活动的最先选择中
for i in range(1,len(li)):
if li[i][0] >= activities_final_choose[-1][1]: # 判断活动开始时间是否大于已排好的最后一个活动的结束时间
activities_final_choose.append(li[i])
return activities_final_choose
print(activity_choose(activities))
贪心算法总结
需要get到该问题是贪心的，知道贪啥，按啥来贪
上述问题采用的贪心算法的共同点：
- 都是最优化问题（最多/大，最少/小）
动态规划
待