贪心算法-旅行规划问题

1、上机04实验名称1、问题描述二、旅行规划问题G先生想独自驾驶汽车从城市A到城市B.从城市A到城市B地距离为dkm.汽车油箱地容量为c升.每升汽车能行驶ekm.出发点每升汽油地价格为p元从城市A到城市B沿途有n个加油站.第i个加油站距出发点地距离为dikm,油价为每升pi元.请利用贪心算法，规划如何加油才能使旅行地费用最省，编程实现该算法并证明算法地正确性版权文档，请勿用做商业用途2、算法设计思想贪心算法3、算法过程描述贪心选择性质证明(1) 当油箱屮地油不够到达最近地加油站时此题无解(2) 当油箱地容量与油耗地比够到每一个加油站时此题有解最优解即为用最便宜地油价将车开到终点，所以需要在保证到达

2、下一个加油站时，油箱中地油够用记录在每一个加油站地加油量和油价，汇总后地价格即为最优解版权文档，请勿用做商业用途4、算法实现及运行结果#i nclude nclude elude using n amespace std;typedef struct double pos;double price; double fillc;gasstdti on;gasstati on gasst502:bool cmp(gasstati on a, gasstati on b) if (a. pos b pos)return true;return false;int mai n() double Cma

3、x, D, Davg:int N;printf C汽车油箱容量c:);scan& Cmax):printf(A 到 B 地距离 d* ”)；sea nf，& D);printf C每升汽油能行驶地距离e:);sea nf(%lf, & Davg);printf (“加油站地数量n：0;sea nf (%d, & N);printf (”每个加油站地油价以及到 A地距离d： n, N);for(int i = 0; i N; i卄)sea nf (z，%lf %lf，z, &gassti price, &gass t i pos):sort (gasst, gasst+N, emp);辻(D 二

4、二 0) prin tf(0. 00n);return 0;)if (gasst0. pos != 0)printf C最大行驶距离为：0n);return 0;int curst num = 0;double curgas = 0;double curcost 二 0;bool flag = false;double maxrun dis = Cmax * Davg;while(!flag) bool tag = false;bool ifeheaper = false;double cheapestprice = 10000;int cheapest num;for(i nt i = cu

5、rst num + 1; i N; i+) if (gasst i. pos - gasst curst nu m. pos) = maxrun dis)版权文档，请勿用做商业用途tag = true;if (gasstiprice gasstcurst nu mprice)ifeheaper = true;double dist = gasstipos 一 gasstcurst nu mpos;double n eedgas = dist / Davg - curgas;curgas = 0;curcost +二(n eedgas 水 gasstcurst nu mprice):gasstc

6、urst nu mfi11c = n eedgas;curst num = i;break;if(gasstiprice = (D - gasst curst num. pos)版权文档，请勿用做商业用途double dist 二 D - gasstcurst nu mpos;double n eedgas = dist / Davg - curgas:curcost +二 n eedgas * gasstcurst nu mprice;gasstcurst nu mfi11c = n eedgas;printf (，zn 最小花费为：%. 21fn， curcost):printf(n每个加

7、油站地加油量为：n)；for(int i = 0; i N; i+) prin tf(%. 21fn, gass ti.fillc);return 0:if (tag & !辻(0砂61*)double n eedgas = Cmax - curgas:gasstcurst nu m. fillc = n eedgas:curcost += (n eedgas * gasstcurst nu mJ. price):double dist 二 gasstcheapest nu m.pos - gasstcurst nu m.pos;版权文档，请勿用做商业用途curgas 二 Cmax - dist / Davg;curst num = cheapest num;else if(!tag)printf (最丿7彳丁驶目巨罔为：%. 21fn，z, gass