旅游预算算法--附源码

描述一个旅行社需要估算乘汽车从某城市到另一城市的最小费用，沿路有若干加油站，每个加油站收费不一定相同。旅游预算有如下规则：1、若油箱的油过半(超过一半)，不停车加油，除非油箱中的油不可支持到下一站；注意加油或者不加油的条件：1)不管是否过半，只要支撑不到下一站就得加油，或者油箱不过半也可以加油。2)只要能支撑到下一站就可以不加油。2、每次加油时都加满；3、在一个加油站加油时，司机要花费2元买东西吃；司机不必为其他意外情况而准备额外的油；汽车开出时在起点加满油箱；计算精确到分（1元=100分）。编写程序估计实际行驶在某路线所需的最小费用。输入第一行为起点到终点的距离（实数）第二行为三个实数，后跟一个整数，每两个数据间用一个空格隔开。其中第一个数为汽车油箱的容量（升），第二个数是每升汽油行驶的公里数，第三个数是在起点加满油箱的费用（精确到分），第四个数是加油站的数量。（〈=50）。接下去的每行包括两个实数，每个数据之间用一个空格分隔，其中第一个数是该加油站离起点的距离，第二个数是该加油站每升汽油的价格（元/升）。加油站按它们与起点的距离升序排列。所有的输入都有一定有解。输出共两行，每行都有换行第一行为一个实数和一个整数，实数为旅行的最小费用，以元为单位，精确到分，整数表示途中加油的站的N。第二行是N个整数，表示N个加油的站的编号，按升序排列。数据间用一个空格分隔，最后一个数据后也输出空格，此外没有多余的空格。输入样例516.315.722.120.873125.41.259297.91.129345.20.999输出样例38.0912问题分析：1）加油站采用结构体比较方便2）用数组a来记录是否在该站加油了3）Double数组b来表示可能路径的费用，并需要比较记录最小费用路径的信息4）还需要记录下每个站点剩下的油源码：#includestdio.hstructgstation{intnum;//numberofgasstationdoubledis;//distancetothestartdoublefee;//costofperL}GS[51];intcount=0,n;doubleb[1000]={0};//costofoneroutinedoublerestv[51];//therestofoilwhenarrivedtoNO.istationdoubledistance;doublevolume,MilesPerL,cost1;inta[51],c[51];//stateofgasstationdoublemin=100000;voidcheck(){inti;for(i=1;i=n;i++)if(a[i]==1){b[count]+=(volume-restv[i])*GS[i].fee+2;}b[count]+=cost1;if(b[count]min){min=b[count++];for(i=1;i=n;i++)c[i]=a[i];}}voidsearch(intm){if(mn)check();elseif(mn){if(restv[m]*MilesPerL=GS[m+1].dis-GS[m].dis){a[m]=0;restv[m+1]=restv[m]-(GS[m+1].dis-GS[m].dis)/MilesPerL;search(m+1);}if(restv[m]*MilesPerLGS[m+1].dis-GS[m].dis||restv[m]=0.5*volume)//attention:therestofoilmustbe=halfofthevolume!{a[m]=1;restv[m+1]=volume-(GS[m+1].dis-GS[m].dis)/MilesPerL;search(m+1);}}else{if(restv[m]*MilesPerL=distance-GS[m].dis){a[m]=0;search(m+1);}else{a[m]=1;search(m+1);}}}intmain(){inti,j=0,flag=0;scanf(%lf,&distance);scanf(%lf%lf%lf%d,&volume,&MilesPerL,&cost1,&n);for(i=1;i=n;i++){scanf(%lf%lf,&GS[i].dis,&GS[i].fee);GS[i].num=i;}restv[1]=volume-GS[1].dis/MilesPerL;search(1);for(j=1;j=n;j++)if(c[j]==1)flag++;printf(%.2lf%d\n,min,flag);for(j=1;j=n;j++)if(c[j]==1)printf(%d,j);//printf(%d,c[n]);printf(\n);return0;}