1.贪心算法 在对问题求解时，总是作出在当前看来是最好的选择。也就是说，不从整体上加以考虑， 它所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。
基本思路：
1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。
2.最优装载问题 有一天海盗们截获了一艘装满各种各样古董的货船，每一件都价值连城，一旦打碎就是去了价值，海盗船载重量为C，每件固定的重量为wi，海盗们该如何尽可能装载最多数量的古董呢？
船载重量固定为C，只要每次选择重量最小的古董，直到不能再装为止，这样装载的古董数量最大,这就是贪心策略；
把古董按重量从小到大排序，根据策略选出尽可能多的古董。
# 定义每个古董重量 antique = [4, 10, 7, 11, 3, 5, 14, 2] def max_ans(antique): anti_sort = sorted(antique) # 对重量排序 ans, tmp = 0, 0 # ans记录装载古董数量，tmp记录装载古董重量 ship = [] # 记录装载的古董 for a in anti_sort: tmp += a if tmp <= 30: ans += 1 ship.append(a) print('装载古董数量:', ans) print('装载的古董', ship) max_ans(antique)3.教室调度问题 你希望在这间教室上尽可能多的课。如何选出尽可能多且时间不冲突的课程呢？ 具体做法如下： (1) 选出结束最早的课，它就是要在这间教室上的第一堂课。 (2) 接下来，必须选择第一堂课结束后才开始的课。同样，你选择结束最早的课，这将是要在这间教室上的第二堂课。 重复这样做就能找出答案！
贪婪算法很简单：每步都采取最优的做法。在这个示例中，你每次都选择结束最早的 课。用专业术语说，就是你每步都选择局部最优解，最终得到的就是全局最优解。
4.背包问题 假设山洞中有n种宝物，每种宝物有一定重量w和相应的价值v，毛驴运载能力 一种宝物只能拿一样，宝物可分割。怎样才能使毛驴运走宝物的价值最大呢？
可以尝试三种贪心策略：
每次挑选价值最大的装东西入背包；每次挑选最重的东西；每次选取单位重量价值最大的东西。我们采用单位重量价值最大的策略
计算出每件宝物的性价比，按照从高到低排序；
根据贪心策略，按性价比从大到小选取宝物，直到达到毛驴的运载能力。每次选择宝物后判断是否小于m，如果不小于则取走宝物的一部分，程序结束。
# datas中每个元素代表一个古董，每个列表第一个元素代表古董重量，第二个元素代表古董价值 datas = [[4, 3], [2, 8], [9, 18], [5, 6], [5, 8], [8, 20], [5, 5], [4, 6], [5, 7], [5, 15]] m = 30 # 毛驴运载能力 w = 0 # 获取的总价值 # 计算出每件宝物的性价比，按照从高到低排序 for i in range(len(datas)): price = datas[i][1] / datas[i][0] datas[i].append(price) # 增加性价比 datas.sort(key=lambda data: data[2], reverse=True) # 按性价比排序 # 按性价比从大到小选取宝物，直到达到毛驴的运载能力 for data in datas: if data[0] <= m: w += data[1] m -= data[0] else: w += data[2] * m # 取走宝物的一部分 break print('总价值：',w)想一下如果宝物不可分割，贪心算法得到的是否是最优解？
注意: 物品可分割的装载问题称为背包问题，不可分割问题的装载问题称为0-1背包问题。 0-1背包问题不具有贪心选择性质，贪心算法不能得到全局最优解，仅仅是最优解的近似解。 0-1背包问题可用动态规划算法求解。
