《贪心算法旅行加油问题》由会员分享，可在线阅读，更多相关《贪心算法旅行加油问题（11页珍藏版）》请在金锄头文库上搜索。
1、旅行规划问题,G 先生想独自驾驶汽车从城市A 到城市B。从城市A 到城市B 的距离为d0 公里。汽车油箱的容量为c 公升。每公升汽油能行驶e 公里。出发点每公升汽油的价格为p 元。从城市A到城市B 沿途有n 个加油站。第i 个加油站距出发点的距离为di，油价为每公升pi元。如何规划才能使旅行的费用最省。,编程任务： 对于给定的d0,c,e,p,和n 以及n个加油站的距离和油价di 和pi，编程计算最小的旅行费用。如果无法到达目的地，输出“No Solution”。,Sample input 275.6 11.9 27.4 2.8 2 102.0 2.9 220.0 2.2 Sample out
2、put 26.95 ci0=220.0/27.4=8.029 ci1=0 ci2=(275.6-220)/27.4=2.029 Total = 8.029*2.8 + 2.029*2.2 = 26.95,第一步：判断旅行家能否到达目的地 假设在任一个加油站都加满油，能否到达终点,第二步：预算最少费用 采用贪心算法的思想求解,汽车在到达目的地之前的每一时刻，都必须保证油箱中的汽油足够行驶到下一油站。 如果以p(i)表示第i油站的汽油价格，x(i)表示在第i油站所加汽油的量，总费用为 P p(i) * x(i) i=0,1,.,n,两个城市之间的距离是固定不变的，汽车从出发点到达目的地所需要的汽油
3、总量（即x(i) i=0,1,.,n ）自然也是固定不变的。 根据使费用最少的求解目标，要使费用函数取得最优值（在此为最小值），必须使p(i)尽可能小：也就是汽车要尽可能在价格便宜的油站加油。,汽车每到达一个油站i（包括出发点第0站，但不包括目的地第n+1站），都要检查是否需要加油。,如果汽车在某个油站i需要加油，那么，就先将该油站的汽油价格p(i)与下一油站的汽油价格p(i+1)进行比较，若p(i)=p(i+1)，加油时，只需保证油箱中的汽油能够到达下一油站（第i+1站）即可； 否则，继续将p(i)与第i+2站的汽油价格p(i+2)进行比较，,判断是否需要在第i站加油的条件可以确定为：在到达第i站时，汽车油箱中的剩余汽油（用变量rest表示剩余汽油的多少）是否足够行驶到下一更便宜的油站j，即rest*e是否大于或等于d(j)-d(i)。 如果一直找不到比第i个油站更便宜的油站j，则在第i个油站加满油（如果不用加满就已经到了终点，则加油量应该满足刚好到达终点）,
