试题详情
简答题G先生想独自驾驶汽车从城市A到城市B。从城市A到城市B的距离为d0公里。汽车油箱的容量为c公升。每公升汽油能行驶e公里。出发点每公升汽油的价格为p元。从城市A到城市B沿途有n个加油站。第i个加油站距出发点的距离为di，油价为每公升pi元。请设计一个算法使到G先生旅行的费用最省（这里的旅行费用指的是加油的总花费）。
  • 第一步：判断旅行家能否到达目的地
    假设在任一个加油站都加满油，能否到达终点
    第二步：预算最少费用
    采用贪心算法的思想求解
    汽车在到达目的地之前的每一时刻，都必须保证油箱中的汽油足够行驶到下一油站。
    如果以p（i）表示第i油站的汽油价格，x（i）表示在第i油站所加汽油的量，总费用为P＝∑p（i）*x（i）i=0，1，….，n。
    两个城市之间的距离是固定不变的，汽车从出发点到达目的地所需要的汽油总量（即∑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个油站加满油（如果不用加满就已经到了终点，则加油量应该满足刚好到达终点）。

  • 关注下方微信公众号，在线模考后查看

热门试题