企业网站seo案例,深圳营销型网站推广,中文 wordpress 主题,免费手机网站app向日葵朝着太阳转动#xff0c;时刻追求自身成长的最大可能。
贪心策略在一轮轮的简单选择中#xff0c;逐步导向最佳答案。
课堂学习
引入 贪心算法#xff08;英语#xff1a;greedy algorithm#xff09;#xff0c;是用计算机来模拟一个「贪心」的人做出决策的过程…
向日葵朝着太阳转动时刻追求自身成长的最大可能。
贪心策略在一轮轮的简单选择中逐步导向最佳答案。
课堂学习
引入 贪心算法英语greedy algorithm是用计算机来模拟一个「贪心」的人做出决策的过程。这个人十分贪婪每一步行动总是按某种指标选取最优的操作。而且他目光短浅总是只看眼前并不考虑以后可能造成的影响。
可想而知并不是所有的时候贪心法都能获得最优解所以一般使用贪心法的时候都要确保自己能证明其正确性。
解释
适用范围
贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决子问题的最优解能递推到最终问题的最优解。1
证明
贪心算法有两种证明方法反证法和归纳法。一般情况下一道题只会用到其中的一种方法来证明。
反证法如果交换方案中任意两个元素/相邻的两个元素后答案不会变得更好那么可以推定目前的解已经是最优解了。归纳法先算得出边界情况例如 的最优解 然后再证明对于每个 都可以由 推导出结果。
要点
常见题型
在提高组难度以下的题目中最常见的贪心有两种。
「我们将 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,sum0;
int main(){for(int i1;i4;i){cinn;int t0; //定义一个变量存储每堆胡萝卜重量的最大值。for(int j1;jn;j){cina[j]; //输入胡萝卜的重量//胡萝卜的重量大于t就更新t的值。求出每一堆的最优结果。if(a[j]t) ta[j];}sumt; //累加每堆最重胡萝卜的重量得到最终的最优结果。}coutsumendl;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和船载重量cinnc;//输入n个士兵兔体重for(int i0; in; i)cinw[i];//按照体重升序排序sort(w,wn);//tmp计算上船的总体重ans数量int tmp0,ans0;for(int i0; in; i) {//从体重最小士兵开始依次上船tmpw[i];//上船士兵兔总重量小于载重量if(tmpc)ans; //统计士兵数量elsebreak; //否则终止循环}coutans;return 0;
}
4454 上船问题
描述
有 n 个人需要过河第 i 个人的体重为wi河边有很多船每艘船的最大载重为m且最多可以上两个人问最少需要多少艘船。
输入描述
第一行输入两个整数 n 和 m表示人数和船的载重。 第二行 n 个整数用空格隔开表示体重。
输出描述
一个整数表示需要的最少船只。
样例输入 1
6 120
15 17 102 70 90 68
样例输出 1
4
提示
数据范围与提示
1≤n,m≤2001≤wi≤100wi≤m
#includebits/stdc.h
using namespace std;
int n,m;
int a[201];
int main()
{//n为人数m为一条船的最大承重cinnm;//输入体重for(int i1;in;i) cina[i];//体重从小到大排序sort(a1,an1);//i表示最轻体重下标位置j表示最重体重下标位置int i1,jn;//记录所用船数int cnt0;//遍历所有船员while(ij){//判断最轻和最重船员是否超过载重if(a[i]a[j]m) {j--;//超过载重就选择更轻的船员cnt;//记录船的数量}else{//切换下一组最轻、最终i;j--;cnt;//记录船的数量}}//输出最终解coutcntendl; 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(){cinn;for(int i0;in;i)cina[i];sort(a,an);//按照答疑时间升序排序int s0;for(int i0;in;i){//第1个人的答疑时间乘以n,等于自己的答疑时间和后面人的等待时间 s(n-i)*a[i];//计算所有人的总时间}printf(%.2f,s*1.0/n);return 0;
}
4453 购物竞赛
描述
某大型卖场在节日期间举行购物竞赛参赛者可以推着购物车在卖场中选择提前罗列好的商品可选商品有 N 种每种商品的总价为 M 元被拆分成均等的 K 个包装现在购物车里可以装的包装数量被固定为 L 个问怎么选才能使购物车中的价值最大。
输入描述
第一行输入整数 N 和 L用空格隔开。 第二行到第 N1 行每行两个整数 M 和 K用空格隔开。
输出描述
一个整数购物车中可以装载的最大价值。
样例输入 1
5 10
12 6
8 2
20 4
7 7
15 5
样例输出 1
40
提示
数据范围与提示
1≤N,L≤1001≤M,K≤100M%K0
#includebits/stdc.h
using namespace std;
//创建表示商品属性的结构体
struct cmdt{int price, num, ave;
}box[110];
//排序规则-单价从大到小排序
bool cmp(cmdt x, cmdt y) {return x.avey.ave;
}
int main() {int n0, l0, sum0;cinnl;for (int i0; in; i) {//输入商品价值及数量cinbox[i].pricebox[i].num;//计算商品单价box[i].avebox[i].price/box[i].num;}//按照单价从大到小排序sort(box, boxn, cmp);//遍历商品种类for (int i0; in; i) {//当前商品价值全部累加if (box[i].numl) {sumbox[i].price;l-box[i].num;//当前商品价值部分累加} else {sumbox[i].ave*l;break;}}coutsum;return 0;
}
课后作业
2381 可可岛的宝藏
描述
可可岛位于距哥斯达黎加海岸300英里的海中曾是17世纪海盗的休息站海盗们将掠夺的财宝在此装装卸卸埋埋藏藏为这个无名小岛平添了神秘色彩据说岛上至少埋有6处宝藏。某天童童历经千难万险到了可可岛上上面有许多珍贵的金属童童虽然更喜欢各种宝石的艺术品可是也不拒绝这样珍贵的金属。但是他只带着一个口袋口袋至多只能装重量为w的物品。岛上金属有 s 个种类, 每种金属重量不同分别为 n1,n2,…,ns同时每个种类的金属总的价值也不同分别为 v1,v2, …, vs。童童想一次带走价值尽可能多的金属问他最多能带走价值多少的金属。注意到金属是可以被任意分割的并且金属的价值和其重量成正比。
数据范围与提示 1≤w≤100001≤s≤1001≤ni≤100001≤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≤100001≤s≤1001≤ni≤100001≤vi≤10000
#includebits/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.py.p;}//按照单位价值降序排序
int main(){cink;//输入k组数据while(k--){cinws;double sum0;//在while循环里面初始化for(int i1;is;i){cinb[i].weib[i].v;b[i].pb[i].v*1.0/b[i].wei;//计算单位价值}//排序sort(b1,bs1,my_cmp);for(int i1;is;i){if(w-b[i].wei0){//能装入w-b[i].wei;//装入减去物品重量sumb[i].v;//计算装入物品的价值}else{//不能装入sumw*b[i].p;//装一部分break;//终止循环}}printf(%.2f\n,sum);//输出一定要加换行}return 0;
}
1547 童程同学讲礼貌
描述
童程学校的学生非常遵守学校的规章制度。小朋友们课间喝水都去排队打水但是条件很有限只有一台饮水机。为了珍惜有限的课余时间老师想到了一个办法让同学们的平均等待时间最少。现在有 n 个小朋友在一个饮水机前排队接水假如每个人接水的时间为 Ti请你编程帮老师找出这 n 个小朋友排队的一种顺序使得 n 个人的平均等待时间最小。(需要考虑自己打水的时间)
输入描述
输入文件共两行第一行为 n1≤n≤1000 第二行分别表示第 1 个同学到第 n 个同学每人的接水时间 T1T2…Tn每个数据之间有 1 个空格0Ti≤1000。
输出描述
输出文件有一行为老师得到的某种排列方案下的最小平均等待时间(输出结果精确到小数点后两位)。
样例输入 1
10
56 12 1 99 1000 234 33 55 99 812
样例输出 1
532.00
提示
数据范围与提示 1≤n≤10000Ti≤1000。
#includebits/stdc.h
using namespace std;
int a[1010],n;
int main(){cinn;for(int i1;in;i)cina[i];//按照打水时间排序sort(a1,an1);int s0;for(int i1;in;i){//计算等待时间s(n-i1)*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≤1001≤wi≤100wi≤y
#includebits/stdc.h
using namespace std;
int main(){int a[105]{};int n,y;cinny;for(int i1;in;i) cina[i];sort(a1,an1); //按礼物价值升序int i1,jn; //i表示价值最小礼物 j表示价值最大礼物int two0; //表示两个礼物一组的组数while(ij){if(a[i]a[j]y) //价值和超过y价值高的自己1组 j--;else{ //没有超过y两个礼物放1组i;j--;two;}}couttwo;return 0;
}
1743 童童看节目
描述
寒假到了童童终于可以开心的看电视节目了。寒假播放的少儿节目太多了童童想尽量多的看到这些节目但是童童有个习惯他只看完整的节目。 现在他把他喜欢的电视节目的转播时间表给你你能帮他合理安排吗
数据范围与提示 n≤100
输入描述
输入包含多组测试数据。每组输入的第一行是一个整数 nn≤100表示童童给你的节目表上节目的总数。 接下来 n 行每行输入两个整数 si 和 ei1≤i≤n表示第 i 个节目的开始和结束时间为了简化问题每个时间都用一个正整数表示。 当 n0 时输入结束。
输出描述
对于每组输入输出能完整看到最多多少个节目。
样例输入 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
#includebits/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.ey.e;else return x.sy.s;
}
int main(){int n;cinn;while(n!0){ //n不等于0就继续for(int i1;in;i)cina[i].sa[i].e;sort(a1,an1,cmp); //结束时间早的在前int s1;//统计节目数量默认第1可以看Node ta[1];//t记录已统计的最后1个节目for(int i2;in;i){//当前节目开始时间不小于t的结束时间if(a[i].st.e){s;ta[i];}}coutsendl;cinn; //输入下1组n如果n0则退出while}return 0;
}
