目录
一、前言
二、贪心法
1、优缺点
2、例子：最少硬币问题
3、贪心和动态规划
4、例题：快乐司机（lanqiaoOJ题号1513）
5、例题：旅行家的预算（lanqiaoOJ题号775）
三、例题
1、翻硬币（lanqiaoOJ题号209）
（1）思路：BFS？
（2）思路：贪心
2、防御力（lanqiaoOJ题号226，2018年国赛）
（1）贪心法编程
一、前言
贪心法是从问题的某一个初始解出发，在每一个阶段都根据贪心策略来做出当前最优的决策，逐步逼近给定的目标，尽可能快地求得更好的解。当达到算法中的某一步不能再继续前进时，算法终止。贪心法可以理解为以逐步的局部最优，达到最终的全局最优。
二、贪心法
1、优缺点
【算法优点】
容易理解：生活常见
操作简单：在每一步都选局部最优
效率高：复杂度常常是 O(1) 的
【算法缺点】
缺点：局部最优不一定是全局最优
2、例子：最少硬币问题
硬币面值 1、2、5。支付 13 元，要求硬币数量最少。
贪心：
（1）5元硬币，用2个
（2）2元硬币，用1个
（3）1元硬币用一个
硬币面值 1、2、4、5、6。支付9元。
贪心：
（1）6元硬币，1个
（2）2元硬币，1个
（3）1元硬币，1个。
错误！答案是：5元硬币+4元硬币
故硬币问题的正解应该是动态规划！
3、贪心和动态规划
贪心法求解的问题满足以下特征：
最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。从局部最优能扩展到全局最优。贪心选择性质。问题的整体最优解可以通过一系列局部最优的选择来得到。
动态规划：
重叠子问题：子问题是原大问题的小版本；计算大问题的时候，需要多次重复计算小问题。最优子结构：大问题的最优解包含小问题的最优解；可以通过小问题的最优解推导出大问题的最优解。
4、例题：快乐司机（lanqiaoOJ题号1513）
【题目描述】话说现在当司机光有红心不行，还要多拉快跑。多拉不是超载，是要让所载货物价值最大，特别是在当前油价日新月异的时候。司机所拉货物为散货，如大米、面粉、沙石、泥土… 现在知道了汽车核载重量为 w，可供选择的物品的数量 n。每个物品的重量为 gi，价值为 pi。求汽车可装载的最大价值。(n<10000, w<10000, 0 【输入描述】输入第一行为由空格分开的两个整数 n,w。第二行到第 n+1 行，每行有两个整数，由空格分开，分别表示 gi 和 pi。 【输出描述】最大价值（保留一位小数）。 n,w=map(int,input().split()) a=[] for i in range(n): gp=list(map(int,input().split())) #读重量、价值 a.append(gp) a.sort(key=lambda x:x[1]/x[0],reverse=True) #结构体排序，按单价从大到小排序 val=0 #最大价值 for k in a: #装货，从最贵的到最便宜的 if k[0] val+=k[1] w-=k[0] #计算卡车余重 else: val += w*k[1]/k[0] #散货可以不装完 break print('%.1f'%val) 5、例题：旅行家的预算（lanqiaoOJ题号775） 【题目描述】 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离 D1、汽车油箱的容量 C（以升为单位）、每升汽油能行驶的距离 D2、出发点每升汽油价格 P 和沿途油站数 N ( N可以为零 )，油站 i 离出发点的距离 Di、每升汽油价格Pi ( i=1, 2,...N ) 。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出 No Solution。 【输入描述】 第一行， D1, C, D2, P, N。接下来有 N 行。第 i+1 行，两个数字，油站 i 离出发点的距离 Di 和每升汽油价格Pi。 【输出描述】 输出所需最小费用，计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出 No Solution 贪心：找到下一个更便宜 (不是最便宜) 的加油站 k 够开到 k，就只加刚好到 k 的油不够开到 k，就加满油 import sys D1,C,D2,P,N=map(float,input().split()) N=int(N) Di=[0] #每个加油站到起点的距离，初始是起点 Pi=[0] #每个加油站的油价，初始是起点油站的价格 for i in range(N): #读油站距离和价格 d,p=map(float,input().split()) Di.append(d);Pi.append(p) Di.append(D1);Pi.append(0) #加终点 a=[0]*(N+1) #初始化每个加油站的加油量 DIS=C*D2 #满箱油能行驶距离 remain=0 #剩余油量 i=0 while i<=N: to_next=Di[i+1]-D[i] #当前站点到下一站的距离 if to_next>DIS: print('No Solution') sys.exit() #不能到下一站，直接退出 for k in range(i+1,N+2): #搜索油价小于或等于i站的下一个油站k if Pi[k]<=Pi[i]: to_k=Di[k]-Di[i] #当前站点到k站点的距离 break if DIS>=to_k: #一箱油能到k站 oil=to_k/D2 #到k站需要多少油 if remain>oil: #剩下的油能直接到达k站，不用加油 remain-=oil else: a[i]=oil-remain #实际加油 i=k #现在到了k站 else: #不能到达k站，加满油去下一个站点 a[i]=C-remain remain=C-to_next/D2 i+=1 cost=0 #统计油钱 for i in range(N+1): cost+=a[i]*Pi[i] print('%.2f'%cost) 三、例题 1、翻硬币（lanqiaoOJ题号209） 【题目描述】 小明玩"翻硬币"游戏。桌上放着排成一排的若干硬币。用 * 表示正面，用 o 表示反面 (是小写字母，不是零)。比如，可能情形是 **oo***oooo，如果同时翻转左边的两个硬币，则变为oooo***oooo。小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币，那么对特定的局面，最少要翻动多少次呢？约定：把翻动相邻的两个硬币叫做一步操作。 【输入格式】 两行等长的字符串，分别表示初始状态和要达到的目标状态。每行的长度 < 1000. 【输出格式】 一个整数，表示最小操作步数。 【输入样例】 ********** o****o**** 【输出样例】 5 （1）思路：BFS？ 本题求从初始状态到目标状态的最短路径，非常符合 BFS 的特征。如果学过 BFS，很自然地会考虑用 BFS 来解题。但是本题的状态太多，用 BFS 肯定超时。 （2）思路：贪心 如果让小学生做这个游戏，他会简单地模拟翻动的过程：从左边开始，每遇到和目标状态不同的硬币就操作一步，翻动连续两个硬币，直到最后一个硬币。这是贪心法，但是这题用贪心对吗？下面进行分析和证明。 首先分析翻动的具体操作： 1）只有一个硬币不同。例如位置 a 的硬币不同，那么翻动它时，会改变它相邻的硬币 b，现在变成了硬币 b 不一样，回到了“只有一个硬币不同”的情况。也就是说，如果只有一个硬币不同，无法实现。 2）有两个硬币不同。这两个硬币位于任意两个位置，从左边的不同硬币开始翻动，一直翻动到右边的不同硬币，结束。 3）有三个硬币不同。左边两个不同硬币，可以用操作(2)完成翻动；但是最后一个硬币是操作(1)，无法完成。 总结这些操作，得到结论： 1）有解的条件。初始字符串 s 和目标字符串 t 必定有偶数个字符不同。 2）贪心操作。从头开始遍历字符串，遇到不同的字符就翻动，直到最后一个字符。 下面证明这个贪心操作，是局部最优也是全局最优。 首先找到第一个不同的字符。从左边开始找第一个不同的那个字符（记为 Z），Z 左边的字符都相同，不用再翻动。从 Z 开始，右边肯定有偶数个不同的字符。Z 必定要翻动，不能不翻；它翻了之后，就不用再翻动。所以从左到右的翻动过程，每次翻动都是必须的，也就是说这个翻动 Z 的局部最优操作，也是全局最优操作。贪心是正确的。 暴力法 第 6 行和第 7 行翻动连续 2 个字符。其实第 6 行是多余的，因为当遇到一个不同的字符 s[i] 时，翻它的下一个字符 s[i+1] 就行了，不用再管 s[i]。 s=list(input()) t=list(input()) ans=0 for i in range(len(s)-1): if s[i]!=t[i]: #s[i]='*' if s[i]=='o' else 'o' #多余 s[i+1]='*' if s[i+1]=='o' else 'o' #三目运算 ans+=1 print(ans) 2、防御力（lanqiaoOJ题号226，2018年国赛） 【题目描述】 小明最近在玩一款游戏。对游戏中的防御力很感兴趣。直接影响防御的参数为"防御性能"，记作 d，而面板上有两个防御值 A 和 B ，与 d 成对数关系， A=2d，B=3d (注意任何时候上式都成立) 。在游戏过程中，可能有一些道具把防御值 A 增加一个值，有另一些道具把防御值 B 增加一个值。现在小明身上有 n1 个道具增加 A 的值和 n2 个道具增加 B 的值，增加量已知。现在已知第 i 次使用的道具是增加 A 还是增加 B 的值，但具体使用哪个道具是不确定的，请找到一个字典序最小的使用道具的方式，使得最终的防御性能最大。初始时防御性能为 0，即 d=0，所以 A=B=1。 【输入格式】 输入的第一行包含两个数 n1, n2，空格分隔。第二行 n1 个数，表示增加 A 值的那些道具的增加量。第三行 n2 个数，表示增加 B 值的那些道具的增加量。第四行一个长度为 n1+n2 的字符串，由 0 和 1 组成，表示道具的使用顺序。0 表示使用增加 A 值的道具，1 表示使用增加 B 值的道具。输入数据保证恰好有 n1 个 0， n2 个 1。 【输出格式】 对于每组数据，输出 n1+n2+1 行，前 n1+n2 行按顺序输出道具的使用情况，若使用增加 A 值的道具，输出Ax，x 为道具在该类道具中的编号 (从1开始)。若使用增加 B 值的道具则输出 Bx。最后一行输出一个大写字母 E。 【测试】 对于 20% 的数据，字符串长度 <=10000； 对于 70% 的数据，字符串长度 <=200000； 对于 100% 的数据，字符串长度 <=2000000，输入的每个增加值不超过2^30。 【输入样例】 1 2 4 2 8 101 【输出样例】 B2 A1 B1 E （1）贪心法编程 对 Ai 进行结构体排序，先对 Ai 按增加量的从小到大排序，再按下标 (字典序) 排序。对 Bi 进行结构体排序，先对 Bi 按增加量的从大到小排序，再按下标 (字典序) 排序。然后按题目要求的顺序，输出 Ai 和 Bi 分析过程复杂，代码很简单。这一题是蓝桥杯国赛题，分析过程有一点复杂，不过难度不高，参加国赛的大部分人能做出来。 复杂度：很好主要是排序花时间：O(nlogn) def cmp(x): return x[1] n1,n2=map(int,input().split()) a=list(map(int,input().split())) b=list(map(int,input().split())) for i in range(n1): a[i]=(i+1,a[i]) for i in range(n2): b[i]=(i+1,b[i]) a.sort(key=cmp) b.sort(key=cmp,reverse=True) s=input() idx1,idx2=0,0 for i in range(n1+n2): if s[i]=='1': print("B%d"%b[idx1][0]) idx1+=1 else: print("A%d"%a[idx2][0]) idx2+=1 print("E") 以上，贪心法讲解 祝好 文章来源
发表评论