第6次课 贪心算法 A

向日葵朝着太阳转动，时刻追求自身成长的最大可能。

贪心策略在一轮轮的简单选择中，逐步导向最佳答案。

课堂学习

引入

贪心算法（英语：greedy algorithm），是用计算机来模拟一个「贪心」的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。

可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性。

解释

适用范围

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。1

证明

贪心算法有两种证明方法：反证法和归纳法。一般情况下，一道题只会用到其中的一种方法来证明。

1. 反证法：如果交换方案中任意两个元素/相邻的两个元素后，答案不会变得更好，那么可以推定目前的解已经是最优解了。
2. 归纳法：先算得出边界情况（例如 ）的最优解 ，然后再证明：对于每个 ， 都可以由  推导出结果。

要点

常见题型

在提高组难度以下的题目中，最常见的贪心有两种。

• 「我们将 XXX 按照某某顺序排序，然后按某种顺序（例如从小到大）选择。」。
• 「我们每次都取 XXX 中最大/小的东西，并更新 XXX。」（有时「XXX 中最大/小的东西」可以优化，比如用优先队列维护）

二者的区别在于一种是离线的，先处理后选择；一种是在线的，边处理边选择。

排序解法

用排序法常见的情况是输入一个包含几个（一般一到两个）权值的数组，通过排序然后遍历模拟计算的方法求出最优值。

后悔解法

思路是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受。如此往复。

区别

与动态规划的区别

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

小结

• 贪心算法通常用于解决最优化问题，其原理是在每个决策阶段都做出局部最优的决策，以期获得全局最优解。
• 贪心算法会迭代地做出一个又一个的贪心选择，每轮都将问题转化成一个规模更小的子问题，直到问题被解决。
• 贪心算法不仅实现简单，还具有很高的解题效率。相比于动态规划，贪心算法的时间复杂度通常更低。
• 在零钱兑换问题中，对于某些硬币组合，贪心算法可以保证找到最优解；对于另外一些硬币组合则不然，贪心算法可能找到很差的解。
• 适合用贪心算法求解的问题具有两大性质：贪心选择性质和最优子结构。贪心选择性质代表贪心策略的有效性。
• 对于某些复杂问题，贪心选择性质的证明并不简单。相对来说，证伪更加容易，例如零钱兑换问题。
• 求解贪心问题主要分为三步：问题分析、确定贪心策略、正确性证明。其中，确定贪心策略是核心步骤，正确性证明往往是难点。
• 分数背包问题在 0-1 背包的基础上，允许选择物品的一部分，因此可使用贪心算法求解。贪心策略的正确性可以使用反证法来证明。
• 最大容量问题可使用穷举法求解，时间复杂度为  O(n²)。通过设计贪心策略，每轮向内移动短板，可将时间复杂度优化至 O(n)。
• 在最大切分乘积问题中，我们先后推理出两个贪心策略：≥4 的整数都应该继续切分，最优切分因子为 3 。代码中包含幂运算，时间复杂度取决于幂运算实现方法，通常为 0(1)或O(logn)。

课堂训练

2909 贪心的小童 

描述

兔子采集队工作回来，把采集回来的胡萝卜分成 4 堆,小童只能从每堆里拿走 1 根胡萝卜。
小童的目标是拿走总重量最重的 4 根胡萝卜。假如我们知道每根胡萝卜的重量，爱学编程的你来帮帮小童吧。

输入描述

4堆胡萝卜，共4行：每行第一个正整数n，是一堆胡萝卜的数量（≤1000）。后面n个正整数，是每堆胡萝卜中每个胡萝卜的重量（1≤单个胡萝卜重≤100）。

输出描述

请问拿走的4根胡萝卜总重量最大是多少？

样例输入 1 

5 4 3 2 1 6
4 3 2 1 4
6 9 3 2 4 6 3
3 11 2 1

样例输出 1 

30

#include <bits/stdc++.h>
using namespace std;
int a[1001],n,sum=0;
int main(){for(int i=1;i<=4;i++){cin>>n;int t=0; //定义一个变量，存储每堆胡萝卜重量的最大值。for(int j=1;j<=n;j++){cin>>a[j]; //输入胡萝卜的重量//胡萝卜的重量大于t，就更新t的值。求出每一堆的最优结果。if(a[j]>t) t=a[j];}sum+=t; //累加每堆最重胡萝卜的重量，得到最终的最优结果。}cout<<sum<<endl;return 0;
}

2910 士兵突击

描述

森林战争中兔子们决定越过一个无人防守的湖泊偷袭敌人。一共n名士兵，输入每名士兵的体重。只有一艘船，船的载重量一定（需要输入）。只能运输一次，要求能装载最多的士兵，最多能运送多少名士兵？

输入描述

共两行：
第一行输入两个整数，士兵数量和船载重量（小于2000）。
第二行，输入每名士兵的体重（体重<300）。

输出描述

共1行，最多装载多少名士兵。

样例输入 1 

5 11
7 2 6 4 5

样例输出 1 

3

#include <bits/stdc++.h>
using namespace std;
int main() {//定义变量和数组int n,c,w[2001]= {};//输入士兵个数n和船载重量cin>>n>>c;//输入n个士兵兔体重for(int i=0; i<n; i++)cin>>w[i];//按照体重升序排序sort(w,w+n);//tmp计算上船的总体重ans数量int tmp=0,ans=0;for(int i=0; i<n; i++) {//从体重最小士兵开始依次上船tmp+=w[i];//上船士兵兔总重量小于载重量if(tmp<=c)ans++;  //统计士兵数量elsebreak;  //否则终止循环}cout<<ans;return 0;
}

4454 上船问题

描述

有 n 个人，需要过河，第 i 个人的体重为wi，河边有很多船，每艘船的最大载重为m且最多可以上两个人，问最少需要多少艘船。

输入描述

第一行输入两个整数 n 和 m，表示人数和船的载重。
第二行 n 个整数，用空格隔开，表示体重。

输出描述

一个整数，表示需要的最少船只。

样例输入 1 

6 120
15 17 102 70 90 68

样例输出 1 

4

提示

数据范围与提示

1≤n,m≤200，1≤wi​≤100，wi​≤m

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[201];
int main()
{//n为人数，m为一条船的最大承重cin>>n>>m;//输入体重for(int i=1;i<=n;i++) cin>>a[i];//体重从小到大排序sort(a+1,a+n+1);//i表示最轻体重下标位置，j表示最重体重下标位置int i=1,j=n;//记录所用船数int cnt=0;//遍历所有船员while(i<=j){//判断最轻和最重船员是否超过载重if(a[i]+a[j]>m) {j--;//超过载重就选择更轻的船员cnt++;//记录船的数量}else{//切换下一组最轻、最终i++;j--;cnt++;//记录船的数量}}//输出最终解cout<<cnt<<endl;	return 0;
}

2908 节省时间

描述

童程学校的信息奥赛课非常受欢迎。每次午休，学生们都要排队找IT龙老师答疑。有的同学问题简单，答疑时间短。有的同学问题难，答疑时间长。IT龙老师想到了一个办法，让助理老师对每个学生的问题预估一个答疑时长，写成小条给IT龙老师。请你编程帮助IT龙老师，找到一种排队顺序，让同学们的平均答疑完成时间最少（结果保留两位小数）。注意：答疑完成时间=自己的答疑时间+等前面同学的时间。

输入描述

第一行，输入答疑学生数量（学生数量≤1000）。
第二行，助理老师预估的每个学生的答疑时长（时长≤2000 单位分钟）。

输出描述

平均答疑完成时间最少。

样例输入 1 

4
3 1 2 6

样例输出 1 

5.50

#include <bits/stdc++.h>
using namespace std;
int a[1001],n;
int main(){cin>>n;for(int i=0;i<n;i++)cin>>a[i];sort(a,a+n);//按照答疑时间升序排序int s=0;for(int i=0;i<n;i++){//第1个人的答疑时间乘以n,等于自己的答疑时间和后面人的等待时间  s+=(n-i)*a[i];//计算所有人的总时间}printf("%.2f",s*1.0/n);return 0;
} 

4453 购物竞赛

描述

某大型卖场在节日期间举行购物竞赛，参赛者可以推着购物车在卖场中选择提前罗列好的商品，可选商品有 N 种，每种商品的总价为 M 元，被拆分成均等的 K 个包装，现在购物车里可以装的包装数量被固定为 L 个，问怎么选才能使购物车中的价值最大。

输入描述

第一行输入整数 N 和 L，用空格隔开。
第二行到第 N+1 行，每行两个整数 M 和 K，用空格隔开。

输出描述

一个整数，购物车中可以装载的最大价值。

样例输入 1 

5 10
12 6
8 2
20 4
7 7
15 5

样例输出 1 

40

提示

数据范围与提示

1≤N,L≤100，1≤M,K≤100，M%K=0

#include<bits/stdc++.h>
using namespace std;
//创建表示商品属性的结构体
struct cmdt{int price, num, ave;
}box[110];
//排序规则-单价从大到小排序
bool cmp(cmdt x, cmdt y) {return x.ave>y.ave;
}
int main() {int n=0, l=0, sum=0;cin>>n>>l;for (int i=0; i<n; i++) {//输入商品价值及数量cin>>box[i].price>>box[i].num;//计算商品单价box[i].ave=box[i].price/box[i].num;}//按照单价从大到小排序sort(box, box+n, cmp);//遍历商品种类for (int i=0; i<n; i++) {//当前商品价值全部累加if (box[i].num<l) {sum+=box[i].price;l-=box[i].num;//当前商品价值部分累加} else {sum+=box[i].ave*l;break;}}cout<<sum;return 0;
}

课后作业

2381 可可岛的宝藏

描述

可可岛位于距哥斯达黎加海岸300英里的海中，曾是17世纪海盗的休息站，海盗们将掠夺的财宝在此装装卸卸，埋埋藏藏，为这个无名小岛平添了神秘色彩，据说岛上至少埋有6处宝藏。某天童童历经千难万险到了可可岛上，上面有许多珍贵的金属，童童虽然更喜欢各种宝石的艺术品，可是也不拒绝这样珍贵的金属。但是他只带着一个口袋，口袋至多只能装重量为w的物品。岛上金属有 s 个种类, 每种金属重量不同，分别为 n1,n2,…,ns，同时每个种类的金属总的价值也不同，分别为 v1,v2, …, vs。童童想一次带走价值尽可能多的金属，问他最多能带走价值多少的金属。注意到金属是可以被任意分割的，并且金属的价值和其重量成正比。

数据范围与提示：
1≤w≤10000，1≤s≤100，1≤ni≤10000，1≤vi≤10000

输入描述

第1行是测试数据的组数 k，后面跟着 k 组输入。
每组测试数据占3行，第 1 行是一个正整数 w(1≤w≤10000)，表示口袋承重上限。
第 2 行是一个正整数 s(1≤s≤100) ，表示金属种类。
第 3 行有 2s 个正整数，分别为n1,v1,n2,v2,…,ns,vs分别为第一种，第二种，…，第 s 种金属的总重量和总价值 (1≤ni≤10000,1≤vi≤10000)。

输出描述

k 行，每行输出对应一个输入。输出应精确到小数点后 2 位。

样例输入 1 

2
50
4
10 100 50 30 7 34 87 100
10000
5
1 43 43 323 35 45 43 54 87 43

样例输出 1 

171.93
508.00

提示

数据范围与提示：
1≤w≤10000，1≤s≤100，1≤ni≤10000，1≤vi≤10000

#include<bits/stdc++.h>
using namespace std;
struct node{//结构体存储重量和价值int wei,v;//用来存储单位价值double p;
}b[210];
int k,w,s;
bool my_cmp(node x,node y){return x.p>y.p;}//按照单位价值降序排序
int main(){cin>>k;//输入k组数据while(k--){cin>>w>>s;double sum=0;//在while循环里面初始化for(int i=1;i<=s;i++){cin>>b[i].wei>>b[i].v;b[i].p=b[i].v*1.0/b[i].wei;//计算单位价值}//排序sort(b+1,b+s+1,my_cmp);for(int i=1;i<=s;i++){if(w-b[i].wei>=0){//能装入w-=b[i].wei;//装入，减去物品重量sum+=b[i].v;//计算装入物品的价值}else{//不能装入sum+=w*b[i].p;//装一部分break;//终止循环}}printf("%.2f\n",sum);//输出一定要加换行}return 0;
} 

1547 童程同学讲礼貌

描述

童程学校的学生非常遵守学校的规章制度。小朋友们课间喝水，都去排队打水，但是条件很有限，只有一台饮水机。为了珍惜有限的课余时间，老师想到了一个办法，让同学们的平均等待时间最少。现在有 n 个小朋友在一个饮水机前排队接水，假如每个人接水的时间为 Ti，请你编程帮老师找出这 n 个小朋友排队的一种顺序，使得 n 个人的平均等待时间最小。(需要考虑自己打水的时间)

输入描述

输入文件共两行，第一行为 n，1≤n≤1000
第二行分别表示第 1 个同学到第 n 个同学每人的接水时间 T1，T2，…，Tn，每个数据之间有 1 个空格，0<Ti≤1000。

输出描述

输出文件有一行，为老师得到的某种排列方案下的最小平均等待时间(输出结果精确到小数点后两位)。

样例输入 1 

10                                    
56 12 1 99 1000 234 33 55 99 812

样例输出 1 

532.00

提示

数据范围与提示：
1≤n≤1000，0<Ti≤1000。

#include<bits/stdc++.h>
using namespace std;
int a[1010],n;
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];//按照打水时间排序sort(a+1,a+n+1);int s=0;for(int i=1;i<=n;i++){//计算等待时间s+=(n-i+1)*a[i];}printf("%.2f",s*1.0/n);return 0;
}

4458 分配礼物

描述

有 n 件礼物，第 i 件礼物的价值为 wi​，需要给这些礼物进行分组，每组礼物数量不能超过 2、价值不能超过 y，要求组数尽量少，每位同学可以领一组礼物领完为止，问有多少同学领到两个礼物。

输入描述

第一行两个整数 n、y，用空格隔开。
第二行 n 个整数，用空格隔开，表示礼物的价值。

输出描述

一个整数，表示获得两个礼物的人数。

样例输入 1 

5 36
12 35 20 2 25

样例输出 1 

2

提示

数据范围与提示

1≤n,y≤100，1≤wi​≤100，wi≤y

#include<bits/stdc++.h>
using namespace std;
int main(){int a[105]={};int n,y;cin>>n>>y;for(int i=1;i<=n;i++)	cin>>a[i];sort(a+1,a+n+1);  //按礼物价值升序int i=1,j=n; //i表示价值最小礼物 j表示价值最大礼物int two=0; //表示两个礼物一组的组数while(i<j){if(a[i]+a[j]>y) //价值和超过y，价值高的自己1组 j--;else{ //没有超过y，两个礼物放1组i++;j--;two++;}}cout<<two;return 0;
}

1743 童童看节目

描述

寒假到了，童童终于可以开心的看电视节目了。寒假播放的少儿节目太多了，童童想尽量多的看到这些节目，但是童童有个习惯，他只看完整的节目。
现在他把他喜欢的电视节目的转播时间表给你，你能帮他合理安排吗？

数据范围与提示：
n≤100

输入描述

输入包含多组测试数据。每组输入的第一行是一个整数 n（n≤100），表示童童给你的节目表上节目的总数。
接下来 n 行，每行输入两个整数 si 和 ei（1≤i≤n，表示第 i 个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。
当 n=0 时，输入结束。

输出描述

对于每组输入，输出能完整看到最多多少个节目。

样例输入 1 

12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
5
1 5
2 6
5 8
7 13
9 12
0

样例输出 1 

5
3

#include<bits/stdc++.h>
using namespace std;
struct Node{int s;int e;
};
Node a[105];
bool cmp(Node x,Node y){if(x.e!=y.e)	return x.e<y.e;else	return x.s<y.s;
}
int main(){int n;cin>>n;while(n!=0){ //n不等于0就继续for(int i=1;i<=n;i++)cin>>a[i].s>>a[i].e;sort(a+1,a+n+1,cmp); //结束时间早的在前int s=1;//统计节目数量，默认第1可以看Node t=a[1];//t记录已统计的最后1个节目for(int i=2;i<=n;i++){//当前节目开始时间不小于t的结束时间if(a[i].s>=t.e){s++;t=a[i];}}cout<<s<<endl;cin>>n; //输入下1组n，如果n=0则退出while}return 0;
}