贪心算法

一辆汽车从北京到广州，中间有若干个加油站，油价价格不定，可能高可能低，怎样计算花费最省，又能达到目的地

解决方案 »

  1.   

    计算一流线上相邻两组中最小结果，然后提取出来就是“贪心算法”原理
      

  2.   

    不能先查资料，做调查吗？？？
      

  3.   

    装火车运，花费最省，一辆火车可以装好多汽车~
      

  4.   

    玩彩票的方法（倍投法）：
    先买1桶油，如果下一加油站便宜，买2桶油，只要便宜都加倍买，以此类推
    如果贵就只买一桶(够用就行，如存量多，价格太贵，可不买）
    玩股票的方法（高抛低吸）
    先买10桶油，如果下一加油站便宜，再买10桶油，以此类推
    如果油价高，就卖掉10桶油（留够用的），也以此类推
    因参数待定，具体代码无法给出，
      

  5.   

    应该要知道 ：路程有多远，油箱容量，每分里油耗，每个家油站的价格，起步时油箱存油量 才能计算出绝对正确的结果。
    缺一不可
      

  6.   

    说白了，这个算法就是让你在行动前给出明确的具体结果计算公式，而不是一个空洞的所谓原则。
      

  7.   

    玩股票也能指导最短路径算法？呵呵，根本是个稀里糊涂自欺欺人的加油算法！
      

  8.   

    把汽车卖了,直接坐火车,这样不仅不花钱,而且赚大发了.
    别走路,走路需要很久,路途的费用很高的,坐火车最划得来.
    如果你是美女,可以搭顺风车.连火车票都免了.
      

  9.   

    这个问题是要油价最低，而不包括走路费用吧？
      

  10.   

    没有说油价最低吧"怎样计算花费最省"
      

  11.   

    其实对于50个以下中间站，我相信带回溯的任何算法（哪怕最简单的递归算法）都能很快得到结果，比如从第一个点开始，它之后又n个点可以作为下一站，那么最好的路径就是遍历从下一点到目的地的费用加上第一点到下一点的了路径，其中最小值。这就递归计算出最优路径。但是，这是一个复杂度成指数增长，甚至更快。也许根本无法用我的电脑计算100个中间站点，直接出硬件故障了。
      

  12.   

    这个看似平淡的问题需要一个小小的建模 答案也不一定有一个 理想状态下 设定油价短时间内不会增长 加油站不用绕路就在路边 ，复杂度较高
      

  13.   

    题目都说是贪心了，可见不是很难的问题。当前加油站加的油，要足够开到"比当前加油站便宜并且离当前加油站最近"的下一个加油站.
    依次类推，如果没有更便宜的，那就一直加够到终点的。
      

  14.   

    各位高手真是各抒己见，令李某人佩服。
      

  15.   

    可以参考数据结构中带权值的最小路径算法
      

  16.   

    建议LZ去看一下最短路径算法，