试验4旅游预算问题的动态规划算法设计与实现报告

1、实验4旅游预算问题的动态规划算法设计与实现一、实验目的1、基本掌握动态规划法的原理方法；2、能用程序设计语言实现旅游预算问题的动态规划递推算法。二、实验内容1、认真阅读算法设计教材，熟悉动态规划求解问题的递推原理；2、设计用动态规划算法求解旅游预算问题的数据结构和递推程序。旅游预算问题：一个旅行社需要估算乘汽车从某城市到另一城市的最小费用，沿路有若干加油站，每个加油站收费不一定相同。旅游预算有如下规则：若油箱的油过半，不停车加油，除非油箱中的油不可支持到下一站；每次加油时都加满；在一个加油站加油时，司机要花费2元买东西吃；司机不必为其他意外情况而准备额外的油； 汽车开出时在起点加满油箱；计算精

2、确到分(1元=100分)。编写程序估计实际行驶在某路线所需的最小费用。三、求解旅游预算问题的动态规划递推原理从输入数据可以看出，越靠近终点的站，油价越低，我们从最后一个站开始遍历，根据油箱油量判断这个站是否必须加油，如果非必须，那是否可以加油，如果加油，花费是否有减少，进行更新，每个站加油后的最少花费存放到数组costi;而第i个站到第j个站是否加油记录在 marki=j 。四、实验程序的功能模块各个模块：void Init();初始化，将暂存结果数组全部标志为0,花费为0bool Canoil(int i,int j);判断从i到j站能不能加油bool Mustoil(int i,int j

3、) ;/ 该加油站必须加油Search(int k,double pay,int pri,int end) ; /遍历每个站，寻找最佳加油方案void res(int i,int j) ;/查找那个站需要停留void Print();打印需要加油的站点名详细代码:#include<iostream>#include<stdio.h>#include<fstream>using namespace std;using namespace std;距离，油箱容量，每公升油可行驶公里数，在起点加满邮箱的费用double length,capacity,kilome

4、ter,start;加油站数，标志是否经过，标志是去哪个站加油，暂存数组，总花费 int n,flag,mark52,sum=0;加油站信息，花费信息double oil522,cost52;int i,j,k;double pay;int pri,end;void Init()for(int i=0;i<=52;i+)costi=0;marki=0;bool Canoil(int i,int j)/该加油站能不能加油double sum=oilj0-oili0;加油站 i 和 j 的距离double remain=capacity-sum/kilometer; 油箱从 i 到 j 后的

5、剩余容量if(remain<=capacity/2)return 1;return 0;bool Mustoil(int i,int j)该加油站必须加油double sum=oilj+10-oili0;加油站 i 和 j 的距离if(capacity*kilometer<sum) /油箱的油不足以支撑加油站i和j的距离return 1;return 0;void Search(int k,double pay,int pri,int end)for(i=n;i>=0;i-)假设在第i个加油站加满油flag=0;if(i=n)若开始就能到终点，花费为0costi=0;else

6、for(j=i+1;j<=n;j+) if(Mustoil(i,j) / 从 i 到 j 必须加油pay=costj+(oilj0-oili0)/kilometer*oilj1+2;/i 到终点的花费是：j到终点的花费+从i至U j所需油费if(flag=0) /计算最小花费costi=pay; flag=1;marki=j; /i 要到 j 加油 j=n+1;else if(pay<costi)costi=pay; marki=j;j=n+1;else if(Canoil(i,j) /i 到 j 可以加油pay=costj+(oilj0-oili0)/kilometer*oilj

7、1+2;if(flag=0) costi=pay; flag=1; marki=j; else if(pay<costi)costi=pay; marki=j; void res(int i,int j)for(i=0;i<=n;)if(marki!=0)sum+; i=marki;else break;void Print()ofstream f2("out.txt");int j,i;cout<<cost0+start<<" "<<sum<<endl;f2<<cost0+star

8、t<<" "<<sum<<endl;for(i=0;i<=n;)if(marki!=0)cout<<marki;f2<<marki;i=marki;if(i<=n)cout<<" "f2<<" "else break;cout<<endl;void main()ifstream f1("in.txt");获取基本信息f1>>length;cout<<"起点到终点距离：&quo

9、t;<<length<<endl;f1>>capacity>>kilometer>>start>>n;cout<<"输入邮箱容量："<<capacity<<endl;cout<<"每升汽油行驶的公里数 ："<<kilometer<<endl;cout<<"在起点加满邮箱的费用："<<start<<endl;cout<<"力口油站的数量：

10、"<<n<<endl;for(int i=1;i<=n;i+)f1>>oili0>>oili1;cout<<i<<"加油站离起点的距离及其每升汽油的价格cout<<oili0<<" "<<oili1<<endl;Init();oiln+10=length;oil00=0;Search(k,pay,pri,end);res(i,j);Print();五、最终测试数据和测试结果 一 F:道法设计与分析实验乎Debug'旅游电行

11、起点到终点距曷:SIE .3前人邮箱容量丑S 7由由由 ?|1 .1 匕，上匕 SI IV125.4 1.25929?.9 1.129345.2 0_999邕升汽播柠囊的公里物22 律起点加承邮箱的费用见87 鳄矗蠢血喳及疆生 箍由站高起点的距离区其每分 3加油站离起点的距离应其每升Z8.08851ress any key to contimiEin.txt -记事本需息(E)格式516.315. 7 22. 1 20. 87125. 4 1,259297.9 1,129345. 2 0. 999J oul.txt - 记事本文件(F)编辑旧格式(。)菅看(V)智题(H)38.088512六、思考题1、试用C+诩言实现求有向图每对节点之间最短路径的数据结构和动态规划递推算法要求算法能输出每条最短路径节点序列。Floyd算法Dk(I,j尸minDk-1(I,j),Dk-1(I,K)+Dk-1(k,j) typedef structchar vertexVertexNum;int edgesVertexNumVertexNum;顶点表邻接矩阵，可看做边int n,e;图中当前的顶点数和边数MGraph;void Floyd(MGraph g)int AMAXVMAXV;int p