0.引言
贪心是一种解决问题的策略。这种算法通常用来解决一类 易于描述，易于实现的问题。
相比前面说过的DFS深搜，这一类问题也可以穷举所有可能性，并且逐步剪枝选优；但是，这一类问题相比DFS解决的问题，通常可以把一个问题分解为几个子问题，并且每一个子问题的最优解一定可以得出总问题的最优解。
1.贪心策略基本问题
（1）基本思维问题
①硬币支付问题
问题描述：
有1元，5元，10元，50元，100元，500元的硬币各有c1, c5, c10, c50, c100, c500枚
现在要用这些硬币来支付A元，最少需要多少枚硬币？
本题至少存在一种支付方案
输入格式：
第一行输入每一种硬币对应的数量，共6个数
第二行输入要支付的金额A元
输出格式：
一个数，为需要硬币的数量
数据范围：
0 ≤ ci ≤ 109
0 ≤ A ≤ 109
前面讲递归和深搜时，用过一道算法题：硬币表示，虽然名字很像，但是需要的思想不一样。
- 硬币表示是问给定的硬币数和需要表示的总金额，共有多少种方案
- 这道题问的是哪一种方案用到的硬币数量最少，用到的是贪心策略
思路：
- 如果利用暴力算法，可以枚举每一种方法，计算每一种硬币前面的系数之和，维持一个最小量。但是很显然时间复杂度会超时
- 利用贪心策略，每一次都应该选择最优的方案
- 本题每次选择的最优策略是选择最大的面额，这样会使得总体选择的数量最少
代码：
#include<iostream> using namespace std; int coins_num[7]; int coins[7] = {1, 5, 10, 50, 100, 500}; int A, res; int main(){ for(int i = 0; i < 6; i++) cin >> coins_num[i]; cin >> A; for(int i = 5; i >= 0 && A > 0; i--){ if(coins_num[i] != 0 && A - coins[i] >= 0){ res++; coins_num[i]--; A -= coins[i]; i++; } } cout << res << endl; return 0; }
（2）区间相关问题
①区间选择问题（选择不相交区间）
问题描述：
给定N个开区间(a,b)，从中选择尽可能多的开区间，使得这些开区间两两没有交集。如（1，3）、（2，4），（3，5），（6，7)，最多可以选择三个不相交的区间，（1，3），（3，5），（6，7）。
换一种理解方式：
给定N个开区间(a,b)，每一个点代表一个整点，现在有一些工作，每个工作需要一段连续的时间来完成，怎样选工作，才能使整个时间段内完成的工作数更多？每个工作时间不能重合。
解题思路：
- 先按照右端点升序排序，用一个变量记录第一个右端点
- 从这个点开始向右遍历，找到第二个左端点（即开始时间）大于当前右端点（即结束时间）的第一个区间，再从这里开始重复第二步。
代码实现：
#include<iostream> #include<algorithm> using namespace std; typedef struct job{ int start; int stop; }Job; int n; const int MAXN = 1005; Job jobs[MAXN]; bool compareJob(Job j1, Job j2){//比较函数 return j1.stop < j2.stop; } int f(){ int cnt = 1; //至少可以做一个工作 int y = jobs[0].stop; //记录第一个结束时间 for(int i = 1; i < n; i++){ //遍历整个区间 if(jobs[i].start > y){ //找到下一个开始时间在当前结束时间之后的区间 cnt++; y = jobs[i].stop; //指向下一个区间的结束位置 } } return cnt; } int main(){ cin >> n; if(n == 0){ cout << "0" << endl; return 0; } int s[n], t[n]; for(int i = 0; i < n; i++)//输入开始时间 cin >> s[i]; for(int i = 0; i < n; i++)//输入结束时间 cin >> t[i]; for(int i = 0; i < n; i++){ jobs[i].start = s[i]; jobs[i].stop = t[i]; } sort(jobs, jobs+n, compareJob);//根据结束时间排序 cout << f() << endl; return 0; }
②区间选点问题
问题描述：
数轴上有n个闭区间[ai,bi]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。（最少的点命中所有的区间）
分析：
如果区间i内已经有一个点被取到，则称此区间已经被满足，受上一个题的启发，先讨论区间的包含情况。由于小区间被满足时大区间一定也被满足，所以在区间包含的情况下，大区间不需考虑。
把所有的区间按b从小到大排序（b相同时a从小到大排序），则如果出现区间包含的情况，小区间一定排在前面。按照贪心策略：第一个区间应该取最后一个点。
相似问题：【贪心策略例题】ACM_POJ区间选点问题（C++）
③区间覆盖问题
问题描述：
数轴上有n个闭区间[ai,bi]，选择尽量少的区间覆盖一条指定的线段[s,t]。
解题思路：
- 判断有无解
如果某两个区间之间无法衔接造成无法使整个线段得到覆盖，那本题无解。线段开头和结尾很好判断。 - 首先按照起始位置排序，如果用一个区间就可以覆盖整个线段，那就选最长的那个，如果没有则分成若干个子区间。
- 首先找到起始点在线段左端点（记为start）左边或相等的所有区间，然后记录右端点的最大值（记为maxt）。
- 当下一个区间起始点大于现在的start，再从maxt开始往后重复上一个步骤，把start移到maxt位置。直到maxt大于线段右端。
#include<iostream> #include<algorithm> using namespace std; typedef struct interval{ int s; int t; }Inter; const int MAXN = 1001; Inter intervals[1001]; int N, T; bool compareInter(Inter i1, Inter i2){ return i1.s < i2.s || (i1.s == i2.s && i1.t < i2.t); } int minIntervals(){ int res = 0; int start = 1, end = 1, maxt = 0; //首先取总线段的其实位置为start，maxt用来记录当前最大区间长度 for(int i = 0; i < N; i++){ if(intervals[i].s <= start && intervals[i].t > maxt){ //先找到起始位置在start之前的最长区间 end = maxt = intervals[i].t; //把end和maxt都标记到当前区间的最大值 if(maxt >= T){ //如果当前区间已经覆盖整个区间，记录并退出 res++; break; } }else if(intervals[i].s > start){ //由于是按照起始位置排序的，所以当下一个区间起始位置在这个start之后，就说明这一段的最大区间已选好 if(intervals[i].s > end) return -1; //如果下一个区间的开始位置在上一个区间的结束位置之后，那么无法覆盖全部区间，无解返回-1 start = maxt; //如果还有解，再让start从最大上个区间的最后一段开始 res++; //记录 if(maxt > T) break; //已经覆盖整个区间 } } return res; } int main(){ cin >> N >> T; //有n个区间，一共需要覆盖从1到T for(int i = 0; i < N; i++){ //输入每个区间的范围 cin >> intervals[i].s >> intervals[i].t; } sort(intervals, intervals+N, compareInter); //按照起始位置排序 cout << minIntervals() << endl; return 0; }
（3）背包相关问题（动态规划初级）
①最优装载问题
问题描述：
给出n个物体，第i个物体的重量为wi。选择尽量多的物体，使得总重量不超过C。
分析：
由于指关心物体的重量，所以先从轻的开始装，每次选择剩下的里面最轻的，直到装不下为止。
每次选择最优解，一定可以使得最终的解是最优的，这时典型的贪心算法。（由于思想比较简单，就不给代码了，注意要先排序）
②部分背包问题
问题描述：
有n个物体，第i个物体的重量为wi，价值为vi。在总重量不超过C的情况下让总价值尽量高。每一个物体可以只取一部分，价值和重量按比例计算。
分析：
由于这里引入了物体的价值，所以我们考虑的点变成的每次取到的价值。
当然，我们也需要在重量尽可能小的情况下取的价值更大。
一种直观的贪心策略是：优先取“价值除以重量的值”最大的，直到重量和正好为C
③真题演练
问题描述：
现在知道了汽车核载重量为w，可供选择的物品的数量n。每个物品的重量为gi,价值为pi。求汽车可装载的最大价值。（n<10000,w<10000,0
输入：
输入第一行为由空格分开的两个整数n w
第二行到第n+1行，每行有两个整数，由空格分开，分别表示gi和pi
输出：
最大价值（保留一位小数）
样例输入：
5 36 99 87 68 36 79 43 75 94 7 35
样例输出：
71.3
分析：
这道题就是典型的部分背包问题，只是增加了约束条件
代码：
#include<iostream> #include<algorithm> using namespace std; typedef struct value{ double gi; double pi; double valueOf; }V; int w, n; const int MAXN = 10005; V v[MAXN]; bool compareVal(V v1, V v2){ return v1.valueOf > v2.valueOf; } double maxValue(){ double res = 0; for(int cur = 0; cur < n; cur++){ //从价值比最大的开始选 if(v[cur].gi <= w){ //如果还能装得下现在这个物品 res += v[cur].pi; //记录当前的价值 w -= v[cur].gi; //减去相应的重量 }else if(w > 0 && v[cur].gi > w){ //如果当前物品重量超出剩余载重量 res += v[cur].valueOf * w; //记录当前价值 break; //这种情况说明已经装完了 }else if(w <= 0) break; //如果没空了就退出 } return res; } int main(){ cin >> n >> w; for(int i = 0; i < n; i++){ cin >> v[i].gi >> v[i].pi; v[i].valueOf = v[i].pi/v[i].gi; } sort(v, v+n, compareVal); //按照价值比排序 printf("%.1lf\n", maxValue()); return 0; }
2.贪心策略总结
- 贪心策略能解决的问题，往往可以分解为若干个子问题，并且每个子问题的最优解都可以使得总的解最优。
- 相比DFS，贪心策略不需要穷举更多的可能，而是拥有了推知未来的能力，照某一个方案选择每一个子问题一定可以得到答案。
- 贪心也可以理解为“最优子结构”。
3.贪心策略使用时的注意点
从上面的例题可以看出，每次使用贪心策略，都需要按照某一个属性排序，这也是贪心策略使用的前提。因为我们把一个大问题分解为子问题的时候，每次的选择必然会对后面的判断产生影响（后面的选择不会影响当下）。同时，这一类问题往往需要找到“最大”
、“最少”等答案，所以为了避免每次对于优先顺序的查找、降低复杂度，排序是非常必要的。
相比动态规划，贪心策略则没有对历史的解做保留，也就是只需要通过上一步来推导这一步，只顾眼前。动态规划则需要对于每个子问题的最优解做记录，下一步的最优解可能要追溯到更早的子问题的最优解。再进一步拓展还可以联想到记忆搜索，这里就不多说了。
