贪心算法-旅行规划问题.doc

上机04 实验名称1、 问题描述二、旅行规划问题G先生想独自驾驶汽车从城市A到城市B。从城市A到城市B的距离为dkm。汽车油箱的容量为c升。每升汽车能行驶ekm。出发点每升汽油的价格为p元。从城市A到城市B沿途有n个加油站。第i个加油站距出发点的距离为dikm，油价为每升pi元。请利用贪心算法，规划如何加油才能使旅行的费用最省，编程实现该算法并证明算法的正确性。2、 算法设计思想贪心算法3、 算法过程描述贪心选择性质证明（1）当油箱中的油不够到达最近的加油站时此题无解。（2）当油箱的容量与油耗的比够到每一个加油站时此题有解。最优解即为用最便宜的油价将车开到终点，所以需要在保证到达下一个加油站时，油箱中的油够用。记录在每一个加油站的加油量和油价，汇总后的价格即为最优解。4、 算法实现及运行结果 #include #include #include using namespace std;typedef struct double pos; double price; double fillc; gasstation;gasstation gasst502;bool cmp(gasstation a, gasstation b) if(a.pos b.pos) return true; return false;int main() double Cmax,D,Davg; int N; printf(汽车油箱容量c：); scanf(%lf, &Cmax); printf(A到B的距离d：);scanf(%lf, &D);printf(每升汽油能行驶的距离e：);scanf(%lf, &Davg);printf(加油站的数量n：);scanf(%d, &N);printf(每个加油站的油价以及到A的距离d：n, N); for(int i = 0; i N; i+) scanf(%lf %lf, &gassti.price, &gassti.pos); sort(gasst, gasst+N, cmp); if(D = 0) printf(0.00n); return 0; if(gasst0.pos != 0) printf(最大行驶距离为：0n); return 0; int curstnum = 0; double curgas = 0; double curcost = 0; bool flag = false; double maxrundis = Cmax * Davg; while(!flag) bool tag = false; bool ifcheaper = false; double cheapestprice = 10000; int cheapestnum; for(int i = curstnum + 1; i N; i+) if(gassti.pos - gasstcurstnum.pos) = maxrundis) tag = true; if(gassti.price gasstcurstnum.price) ifcheaper = true; double dist = gassti.pos - gasstcurstnum.pos; double needgas = dist / Davg - curgas; curgas = 0; curcost += (needgas * gasstcurstnum.price); gasstcurstnum.fillc = needgas; curstnum = i; break; if(gassti.price = (D - gasstcurstnum.pos) double dist = D - gasstcurstnum.pos; double needgas = dist / Davg - curgas; curcost += needgas * gasstcurstnum.price; gasstcurstnum.fillc = needgas; printf(n最小花费为：%.2lfn, curcost); printf(n每个加油站的加油量为：n); for(int i = 0; i N; i+) printf(%.2lfn,gassti.fillc); return 0; if(tag & !ifcheaper) double needgas = Cmax - curgas; gasstcurstnum.fillc = needgas; curcost += (needgas * gasstcurstnum.price); double dist = gasstcheapestnum.pos - gasstcurstnum.pos; curgas = Cmax - dist / Davg; curstnum = cheapestnum; else if(!tag) printf(最大行驶距离为：%