lab5贪心算法设计与应用.docx
- 文档编号:2523719
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:10
- 大小:53.50KB
lab5贪心算法设计与应用.docx
《lab5贪心算法设计与应用.docx》由会员分享,可在线阅读,更多相关《lab5贪心算法设计与应用.docx(10页珍藏版)》请在冰点文库上搜索。
lab5贪心算法设计与应用
lab5-贪心算法设计与应用
实验五贪心算法设计与应用
一.基本原理的概括
贪心法是一种算法设计技术,通常用于求解最优化问题。
通过一系列选择步骤来构造问题的解,每一步都是对当前部分解的一个扩展,直至获得问题的完整解。
所做的每一步选择都必须满足:
1)可行的:
必须满足问题的约束。
2)局部最优:
当前所有可能的选择中最佳的局部选择。
3)不可取消:
选择一旦做出,在后面的步骤中就无法改变了。
要注意的是,贪心法不能保证总能得到最优解(一系列的局部最优选择不能保证最后得到整体最优解)
二.该类算法设计与实现的要点
贪心算法往往效率高,一般时间复杂性为多项式阶。
贪心算法一般较简单,其关键和难点在于贪心选择策略的确定,以及证明相应的贪心算法确实可求出最优解。
三.实验目的和要求
理解贪心算法的基本原理,掌握贪心算法设计的基本方法及其应用;
四.实验内容
(一)加油问题(ProblemSet1702):
1.问题描述
一个旅行家想驾驶汽车从城市A到城市B(设出发时油箱是空的)。
给定两个城市之间的距离dis、汽车油箱的容量c、每升汽油能行驶的距离d、沿途油站数n、油站i离出发点的距离d[i]以及该站每升汽油的价格p[i],i=1,2,…,n。
设d[1]=0 要花最少的油费从城市A到城市B,在每个加油站应加多少油,最少花费为多少? 2.具体要求 Input 输入的第一行是一个正整数k,表示测试例个数。 接下来几行是k个测试例的数据,每个测试例的数据由三行组成,其中第一行含4个正整数,依次为A和B两个城市之间的距离d1、汽车油箱的容量c(以升为单位)、每升汽油能行驶的距离d2、沿途油站数n(1<=n<=200);第二行含n个实数d1,d2,…,dn,表示各油站离出发点的距离(d1=0);第三行含n个实数p1,p2,…,pn,表示各油站每升汽油的价格。 同一行的数之间用一个空格隔开。 Output 对于每个测试例输出一行,含一个实数,表示从城市A到城市B所要花费的最少油费(输出的结果精确到小数点后一位)。 若问题无解,则输出“NoSolution”。 3.代码如下: #include #defineMAX20 voidlook(floatdis[],floatpir[],intn,intd2,intoil)//dis距离起点距离,pir油价 { inti,j,k; floatpirce=0.0,c1=0,x,c2; for(j=0;j<=n;j++) { for(i=j+1;i<=n;i++) { if(pir[i] { k=i; c2=(dis[k]-dis[j])/d2; if(c2>=oil) { x=oil-c1; } else { x=c2-c1; if(x<0) { x=0; } } pirce=pirce+pir[j]*x; break; } } c1=c1+x-((dis[j+1]-dis[j])/d2); } printf("%.1f",pirce); } voidmain() { intk,i,j,n[MAX],c[MAX],d1[MAX],d2[MAX],length[MAX],flag[MAX]; floatA[MAX][MAX],B[MAX][MAX]; printf("输入测试例个数: \n"); scanf("%d",&k); for(i=0;i { printf("输入第%d个数据: \n",i+1); flag[i]=0; scanf("%d%d%d%d",&d1[i],&c[i],&d2[i],&n[i]); length[i]=c[i]*d2[i]; for(j=0;j { scanf("%f",&A[i][j]); } A[i][n[i]]=d1[i]*1.0; for(j=0;j { scanf("%f",&B[i][j]); } B[i][n[i]]=0.0; printf("\n"); for(j=n[i];j>0;j--) { if(A[i][j]-A[i][j-1]>length[i]) { flag[i]=1; } } if(flag[i]==1) { printf("第%d次结果: ",i+1); printf("NOsolution! \n"); } else { printf("第%d次结果: ",i+1); printf("最少油费: "); look(A[i],B[i],n[i],d2[i],c[i]); } printf("\n"); printf("\n"); } } (二)黑白点的匹配(ProblemSet1714): 1.问题描述 设平面上分布着n个白点和n个黑点,每个点用一对坐标(x,y)表示。 一个黑点b=(xb,yb)支配一个白点w=(xw,yw)当且仅当xb>=xw和yb>=yw。 若黑点b支配白点w,则黑点b和白点w可匹配(可形成一个匹配对)。 在一个黑点最多只能与一个白点匹配,一个白点最多只能与一个黑点匹配的前提下,求n个白点和n个黑点的最大匹配对数。 2.具体要求 Input 输入的第一行是一个正整数k,表示测试例个数。 接下来几行是k个测试例的数据,每个测试例的数据由三行组成,其中第一行含1个正整数n(n<16);第二行含2n个实数xb1,yb1,xb2,yb2,…,xbn,ybn,(xbi,ybi),i=1,2,…,n表示n个黑点的坐标;第三行含2n个实数xw1,yw1,xw2,yw2,…,xwn,ywn,(xwi,ywi),i=1,2,…,n表示n个白点的坐标。 同一行的实数之间用一个空格隔开。 Output 对于每个测试例输出一行,含一个整数,表示n个白点和n个黑点的最大匹配对数。 3.代码如下: #include"iostream.h" #include"math.h" structpoint { doublex,y; }; voidsort(point*a,intn) { inti,j;pointp; for(i=1;i<=n;i++) { for(j=i+1;j { if(a[i].x>a[j].x||(a[i].x==a[j].x&&(a[i].y>a[j].y))) { p=a[i]; a[i]=a[j]; a[j]=p; } } } } doubledis(pointpointw,pointpointb) { doubledist; dist=sqrt(pow((pointb.x-pointw.x),2)+pow((pointb.y-pointw.y),2)); returndist; } intmain() { inti,j,n,k; cin>>n; point*pointw=newpoint[n]; point*pointb=newpoint[n]; int*b=newint[n]; for(i=1;i<=n;i++) cin>>pointb[i].x; for(i=1;i<=n;i++) cin>>pointb[i].y; for(i=1;i<=n;i++) cin>>pointw[i].x; for(i=1;i<=n;i++) cin>>pointw[i].y; sort(pointw,n); for(i=1;i<=n;i++) b[i]=1; intcount=0;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- lab5 贪心 算法 设计 应用