lab5-贪心算法设计与应用

《lab5-贪心算法设计与应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验五贪心算法设计与应用一.基本原理的概括贪心法是一种算法设计技术，通常用于求解最优化问题。通过一系列选择步骤来构造问题的解，每一步都是对当前部分解的一个扩展，直至获得问题的完整解。所做的每一步选择都必须满足：1）可行的：必须满足问题的约束。2）局部最优：当前所有可能的选择中最佳的局部选择。3）不可収消：选择一旦做出，在后面的步骤中就无法改变了。要注意的是，贪心法不能保证总能得到最优解（一系列的局部最优选择不能保证最后得到整体最优解）二.该类算法设计与实现的要点贪心算法往往效率高，一般时间复杂性为多项式阶。贪心算法一般较简单，其关键

2、和难点在于贪心选择策略的确定，以及证明相应的贪心算法确实可求出最优解。三.实验目的和要求理解贪心算法的基本原理，掌握贪心算法设计的基本方法及其应用；四.实验内容（_）加油问题（ProblemSet1702）：1.问题描述一个旅行家想驾驶汽车从城市A到城市B（设出发时油箱是空的）。给定两个城市之间的距离dis、汽车油箱的容量c、每升汽油能行驶的距离d、沿途油站数n、油站i离出发点的距离d[i]以及该站每升汽油的价格p[i],i=l,2,…，n。设d[l]=O

3、最少花费为多少？2.具体要求Input输入的第一行是一个正整数k,表示测试例个数。接下来儿行是k个测试例的数据，每个测试例的数据由三行组成，其中第一行含4个正整数，依次为A和B两个城市之间的距离dl、汽车油箱的容量c（以升为单位）、每升汽油能行驶的距离d2、沿途油站数n（l<=n<=200）；第二行含n个实数dbd2,...,dn,表示各油站离出发点的距离（山=0）；第三行含n个实数pbp2pn,表示各油站每升汽油的价格。同一行的数之间用一个空格隔开。Output对于每个测试例输出一行，含一个实数，表示从城市A到城市B所要花费的最少

4、油费（输出的结果精确到小数点后一位）。若问题无解，则输出“NoSoMion”。3・代码如下：#include#defineMAX20voidlook（floatdis[],floatpir[],intn,intd2,intoil）//dis距离起点距离，pii•油价intij,k;floatpirce=0.0,cl=0,x,c2;for(j=0;j<=n;j++)for(i=j+l;i<=n;i++){if(pir[i]=oil){x

5、=oil-cl;}else{x=c2-cl;if(x<0){x=0;}}pirce=pirce+pir[j]*x;break;}}cl=cl+x-((dis[j+l]-dis[j])/d2);}printf(M%.lf,,pirce);}voidmain(){intk,iJ,n[MAX],c[MAX],dl[MAX],d2[MAX],length[MAX],flag[MAX];floatA[MAX][MAX],B[MAX][MAX];printf(H输入测试例个数：十)；scanf(M%dn,&k);for(i=0;i

6、){printf「输入第％(1个数据:H,i+l);flag[i]=0;scanf(H%d%d%d%dH,&dl[i],&c[i],&d2[i],&n[i]);length[i]=c[i]*d2[i];for(j=0;j0;j-){if(A[i][j]-A[i][j-l]>length[i]){flag[i]=l

7、;if(flag[i]==l){printf(”第％d次结果:printf(MNOsolution!H);}else{printf(”第％d次结果:printf(H最少油费:H);look(A[i],B[i],n[i],d2[i],c[i]);}printf(Hn);printfC^n**);输入测试例个数:為入第丄个数据:1500501040300・0800・01200・04-05-04-04.5第丄次结果：最少油费：640.0输入第2个数据：1000401030500.0750-04.55.04.2第2次结果:NOsol

8、ution?Pressanykeytocontimie(二)黑白点的匹配(ProblemSet1714)：1.问题描述设平面上分布着n个白点和n个黑点，每个点用一对坐标(x,y)表示。一个黑点b二(xb,yb)支配一个白点w=(xw,