贪心策略总结及相关例题讲解（区间相关问题、部分背包问题等、C/C++）

文章目录

0.引言1.几个例题

（1）区间相关问题

①区间选择问题（选择不相交区间）②区间选点问题③区间覆盖问题 （2）背包相关问题

①最优装载问题②部分背包问题③真题演练 2.我对贪心策略的总结3.贪心策略使用时的注意点 0.引言

贪心法是一种解决问题的策略。这种算法通常用来解决一类 易于描述，易于实现的问题。

相比前面说过的DFS深搜，这一类问题也可以穷举所有可能性，并且逐步剪枝选优；但是，这一类问题相比DFS解决的问题，通常可以把一个问题分解为几个子问题，并且每一个子问题的最优解一定可以得出总问题的最优解。

1.几个例题 （1）区间相关问题 ①区间选择问题（选择不相交区间）

问题描述：

给定N个开区间(a,b)，从中选择尽可能多的开区间，使得这些开区间两两没有交集。如（1，3）、（2，4），（3，5），（6，7)，最多可以选择三个不相交的区间，（1，3），（3，5），（6，7）。

换一种理解方式：
给定N个开区间(a,b)，每一个点代表一个整点，现在有一些工作，每个工作需要一段连续的时间来完成，怎样选工作，才能使整个时间段内完成的工作数更多？每个工作时间不能重合。

解题思路：

先按照右端点升序排序，用一个变量记录第一个右端点从这个点开始向右遍历，找到第二个左端点（即开始时间）大于当前右端点（即结束时间）的第一个区间，再从这里开始重复第二步。

代码实现：

#include#includeusing 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#includeusing 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;//如果下一个区间的开始位置在上一个区间的结束位置之后，那么无法覆盖全部区间，无解返回-1start = 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;}

（2）背包相关问题 ①最优装载问题

问题描述：

给出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 3699 8768 3679 4375 947 35

样例输出：

71.3

分析：

这道题就是典型的部分背包问题，只是增加了约束条件

代码：

#include#includeusing 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("%.1lfn", maxValue());return 0;}

2.我对贪心策略的总结

贪心策略能解决的问题，往往可以分解为若干个子问题，并且每个子问题的最优解都可以使得总的解最优。相比DFS，贪心策略不需要穷举更多的可能，而是拥有了推知未来的能力，照某一个方案选择每一个子问题一定可以得到答案。贪心也可以理解为“最优子结构”。 3.贪心策略使用时的注意点

从上面的例题可以看出，每次使用贪心策略，都需要按照某一个属性排序，这也是贪心策略使用的前提。因为我们把一个大问题分解为子问题的时候，每次的选择必然会对后面的判断产生影响（后面的选择不会影响当下）。同时，这一类问题往往需要找到“最大”、“最少”等答案，所以为了避免每次对于优先顺序的查找、降低复杂度，排序是非常必要的。相比动态规划，贪心策略则没有对历史的解做保留，也就是只需要通过上一步来推导这一步，只顾眼前。动态规划则需要对于每个子问题的最优解做记录，下一步的最优解可能要追溯到更早的子问题的最优解。再进一步拓展还可以联想到记忆搜索，这里就不多说了。