lab5_贪心算法设计与的应用

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

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

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

3、城市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对于每个测试例输出一行

4、，含一个实数，表示从城市Ａ到城市Ｂ所要花费的最少油费（输出的结果精确到小数点后一位）。若问题无解，则输出“NoSolution”。3.代码如下：#include#defineMAX20voidlook(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]

5、]){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];pri

6、ntf("输入测试例个数：");scanf("%d",&k);for(i=0;i

7、}B[i][n[i]]=0.0;printf("");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!");}else{printf("第%d次结果：",i+1);printf("最少油费：");look(A[i],B[i],n[i],d2[i],c[i]);}printf("");printf("");}}精彩文档实用

8、标准文案(一)黑白点的匹配（ProblemSet1714）：1.问题描述设平面上分布着n个白点和n个黑点，每个点用一对坐标（x,y）表示。一个黑点b=（xb,yb）支配一个白点w=(xw,yw)当且仅当xb>=xw和yb>=yw。若黑点b支配白点w，则黑点b和白点w可匹配（可形成一个匹配对