贪心算法详解C++版.docx
- 文档编号:9123568
- 上传时间:2023-05-17
- 格式:DOCX
- 页数:24
- 大小:22.90KB
贪心算法详解C++版.docx
《贪心算法详解C++版.docx》由会员分享,可在线阅读,更多相关《贪心算法详解C++版.docx(24页珍藏版)》请在冰点文库上搜索。
贪心算法详解C++版
【例3-1】删数问题
【问题描述】
键盘输入一个高精度的正整数n(n<=240位),去掉其中任意s个数字后剩下的数字按原左右顺序将组成一个新的正整数。
编程对给定的n和s,寻找一种方案,使得剩下的数字组成的数最小。
输入:
N
S
输出:
最后剩下的最小数。
【样例输入】
178543
4
【样例输出】
13
【题解】
由于正整数n的有效位数为240位,所以很自然地采用字符串类型存储n。
那么如何解决哪s位被删呢?
是不是最大的s个数字呢?
为了尽可能的逼近目标,我们选取的贪心策略为:
每一步总是选择一个使剩下数最小的数字删去。
即按高位到低位的顺序搜索,若各位数字递增,则删去最后一个数字;否则删去第一个递减区间的首字符,这样删一位便形成了一个新数字串。
然后回到串首,按上述规则再删下一个数字。
重复以上过程s次为止,剩下的字串便是问题的解了。
【标程】
#include
#include
#include
usingnamespacestd;
chara[100001];
intmain()
{
intn,i,j,l,k;
gets(a);
cin>>n;
l=strlen(a);
for(i=1;i<=n;i++)
{
for(j=0;j
{
for(k=j;k break; } l--; } for(i=0;i { if(a[i]! ='0') { k=i; break; } } for(j=i;j<=l-1;j++)cout< cout< return0; } 【例3-2】取数游戏 【问题描述】 给出2n(n<=100)个自然数(数小于等于30000)。 游戏双方分别为A方(计算机)和B方(对弈的人)。 只允许从数列两头取数。 A先取,然后双方一次轮流取数。 取完时,谁取得的数字总和最大为取胜方;若双方和相同,属于A胜。 试问A方可否有必胜的策略? 输入: 4 79364253 RRRR 键盘输入n以及2*n个自然数。 输出: 3 5 2 4 6 3 9 7 36 19 共3n+2行,其中前3*n行为游戏过程。 每三行分别为A方所取的数和B方所取的数,及B方取数前应给与适当的提示,让游戏者选取那一头的数(L/R—左端或右端)。 最后两行分别为A方取数之和与B方取数之和。 【标程】 programho; varn,i,j,sa,sb,lp,rp,t: longint; ch: char; a: array[1..200]oflongint; begin readln(n); fori: =1to2*ndo read(a[i]); sa: =0; sb: =0; fori: =1tondo begin sa: =sa+a[2*i-1]; sb: =sb+a[2*i]; end; ifsa>=sbthenj: =1 else begin j: =0; t: =sa; sa: =sb; sb: =t; end; lp: =1; rp: =2*n; fori: =1tondo begin if(j=1)and(lpmod2=1)or((j=0)and(lpmod2=0))then begin writeln(a[lp]); inc(lp); end else begin writeln(a[rp]); dec(rp); end; write('B=L/R? '); repeat readln(ch); ifch='L'then begin writeln(a[lp]); inc(lp); end; ifch='R'then begin writeln(a[rp]); dec(rp); end; until(ch='L')or(ch='R'); end; writeln(sa); writeln(sb); end. 【例3-3】活动选择 【问题描述】 假设有一个需要使用某以资源的n个活动组成的集合S,S={1,…,n}。 该资源一次只能被一个活动占用,每一个活动有一个开始时间bi和结束时间ei(bi<=ei)。 若bi>=ej或bj>=ei,则活动i和活动j兼容。 你的任务是: 选择由相互兼容的活动组成的最大集合。 输入: 输入文件名为: act.in,共n+1行,其中第一行为n,第二行到第n+1行表示n各活动的开始时间和结束时间(中间用用空格隔开),格式为: n b1e1 …… bnen 输出: 输出文件名为: act.out,第一行为满足要求的活动占用的时间t,第二行为最大集合中的活动序号,每个数据之间用一个空格隔开。 【样例输入】 11 35 14 1214 812 06 811 610 57 38 59 213 【样例输出】 14 2368 【题解】 我们使用的贪心策略如下。 即每一步总是选择这样的活动来占用资源: 使得余下的未调度时间最大化,是的兼容的活动尽可能多。 为了达到这个目的,我们将n个待选活动按结束时间递增的顺序排序: e1’<=e2’<=…<=en’。 首先将递增序列的活动1进入集合S。 然后依次分析递增序列中的活动2,活动3,……,活动n,每次将与S中的活动兼容的活动加入到集合S中。 我们结合问题的样例输入,先将11个活动的活动号、开始时间、结束时间及递增编号表 按照以上这种贪心策略,贪心选择如下: 时间012345678911121314 选择活动|—|—|—|—|—|—|—|—|—|—|—|—|—| 2————活动2兼容(持续时间1—4),加入S,S={2},t=4 1不兼容,放弃 5不兼容,放弃 8————活动8兼容(持续时间5—7),加入S,S={2,8},t=7 9不兼容,放弃 10不兼容,放弃 7不兼容,放弃 6————活动6兼容(持续时间8—11),加入S,S={2,8,6},t=11 4不兼容,放弃 11不兼容,放弃 3————活动3兼容(持续时间12—14),加入S,S={2,8,6,3},t=14 所以问题的解: t=14,S={2,8,6,3}。 【标程】 #include #include #include usingnamespacestd; structstu { inta; intb; intc; }s[1005]; boolcmp(stux,stuy) { returnx.b } intd[1005]={0}; intmain() { intn,i; scanf("%d",&n); for(i=0;i { scanf("%d%d",&s[i].a,&s[i].b); s[i].c=i+1; } sort(s,s+n,cmp); intsum=0; intmin=s[0].b; sum=s[0].b-s[0].a+1; for(i=1;i { if(min { min=s[i].b; sum=sum+s[i].b-s[i].a+1; } } printf("%d\n",sum); min=s[0].b; d[s[0].c]=1; for(i=1;i { if(min { min=s[i].b; d[s[i].c]=1; } } for(i=1;i<=1005;i++)if(d[i]! =0)printf("%d",i); return0; } 【例3-4】雇用计划 【问题描述】 一位管理项目的经理想要确定每个月需要的工人,他当然知道每月所需的最少工人数。 当他雇用或解雇一个工人时会有一些额外支出。 一旦一个工人被雇佣,即使他不工作,他也将得到工资。 这位经理知道雇佣一个人的费用,解雇一个人的费用和一个个工人的工资。 现在他在考虑一个问题: 为了把项目的费用控制在最低,他将每月雇用或解雇多少个工人。 输入: 输入文件含有三行。 第一行为月数n(1<=n<=12)。 第二行含雇佣一个工人的费用,一个工人的工资和解雇一工人的费用(<=100).第三行含n个数,分别表示每月最少需要的工人数(<=1000)。 每个数据之间用一个空格隔开。 输出: 输出仅一行,表示项目所需的最小总费用。 【样例输入】 3 456 10911 【样例输出】 199 【题解】 我们从第一个月开始,逐月计算现有工人数,先发给这些人工资。 如果雇用新工人,则必须给新上岗工人发放雇用费用;如果削减了部分工人,则必须给下岗工人发放解雇费用。 当月发放的工资+雇佣(或解雇)的费用构成了一个月的总费用。 我们从第一个月开始,逐月累计项目总费用,直至算出n个月的总费用为止。 问题是怎样将这笔费用控制到最低? 这mincost表示最小费用和,初始时mincost=0;now表示现有工人数,初始时now=0;min[i]表示第i个月所需的最小工人数(1<=i<=n);n表示月数;f表示解雇费用;s表示工资;h表示雇用费用。 则我们需要解决下面两个问题: 1.怎样在当月工人数不足情况下确定雇用方案 如果第i个月的所需最小人数min[i]大于现有工人数now,则需要雇佣工人。 为了尽可能减少雇用费用,我们不妨雇用(min[i]-now)个工人,使第i个月工人数正好为min[i];如果min[i]=now,则维持现有工人数now不变。 2.怎样在当月工人数多于的情况下确定解雇方案 我们选取这样的贪心策略去确定: 尽可能少地解雇工人,并且在工资合理支出的前提下尽可能使现有工人数维持在一个最长时间内,以减少雇佣和解雇的额为支出。 【标程】 programhk; vari,j,f,s,h,n,min,c,max: longint; a: array[0..12]oflongint; begin assign(input,'in.txt'); reset(input); assign(output,'out.txt'); rewrite(output); readln(n); a[0]: =0; c: =0; readln(h,s,f); fori: =1tondo read(a[i]); max: =(h+f)divs+1; fori: =1tondo begin ifa[i]>=a[i-1]then c: =c+a[i]*s+(a[i]-a[i-1])*h; ifa[i] begin min: =0; forj: =i+1toi+maxdo if(j<=n)and(a[j]>min)then min: =a[j]; ifmin begin c: =c+f*(a[i]-min); a[i]: =a[i]-min; a[i+1]: =a[i]; end else begin a[i]: =a[i-1];
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 贪心 算法 详解 C+