验证算法的

Question

我研究这个问题，我承认这是加油站问题的一个变种。因此，我使用贪婪算法来解决这个问题。我想问问，如果有人帮我指出我的算法是否正确，谢谢。

我的算法

var x = input.distance, cost = input.cost, c = input.travelDistance, price = [Number.POSITIVE_INFINITY]; 
    var result = []; 

    var lastFill = 0, tempMinIndex = 0, totalCost = 0; 

    for(var i=1; i<x.length; i++) { 
    var d = x[i] - x[lastFill]; 
    if(d > c){ //car can not travel to this shop, has to decide which shop to refill in the previous possible shops 
     result.push(tempMinIndex); 
     lastFill = tempMinIndex; 
     totalCost += price[tempMinIndex]; 
     tempMinIndex = i; 
    } 
    //calculate price 
    price[i] = d/c * cost[i]; 
    if(price[i] <= price[tempMinIndex]) 
     tempMinIndex = i; 
    } 

    //add last station to the list and the total cost 
    if(lastFill != x.length - 1){ 
    result.push(x.length - 1); 
    totalCost += price[price.length-1]; 
    } 

您可以在此链接 https://drive.google.com/file/d/0B4sd8MQwTpVnMXdCRU0xZFlVRlk/view?usp=sharing

Answer 1

首先尝试的算法，关于您的解决方案。

即使在最简单的输入中，也存在一个缺陷。当你决定距离变得太远，你应该在某个时候完成时，你不会更新它的距离和加油站费用。解决方法是简单的：

if(d > c){ 
//car can not travel to this shop, has to decide which shop to refill 
//in the previous possible shops 
     result.push(tempMinIndex); 
     lastFill = tempMinIndex; 
     totalCost += price[tempMinIndex]; 
     tempMinIndex = i; 
     // Fix: update distance 
     var d = x[i] - x[lastFill]; 
    } 

即使有此修复程序，你的算法对一些输入数据失败，这样的：

0 10 20 30 
0 20 30 50 
30 

应该补充上所有的汽油，以降低成本，但它只是填充上最后一个。

经过一番研究，我想出了解决方案。我会尽可能简单地将其解释为使其与语言无关。

1. 理念

对于每一个加油站G我们会统计填充的最廉价的方式。我们将以递归方式做到这一点：对于每个加油站，我们找到所有加油站i，我们可以从中找到G。对于每个i计数最便宜的填充可能和总结填充的成本在G给定的汽油剩下。对于开始加油站成本为0。更正式：

CostOfFilling(x)，Capacity并Position(x)可以从输入数据进行检索。

所以，对于这个问题的答案很简单BestCost(LastGasStation)

代码

现在，JavaScript来让事情更清晰的解决方案。与代码

function calculate(input) 
{ 
    // Array for keeping calculated values of cheapest filling at each station 
    best = []; 
    var x = input.distance; 
    var cost = input.cost; 
    var capacity = input.travelDistance; 

    // Array initialization 
    best.push(0); 
    for (var i = 0; i < x.length - 1; i++) 
    { 
     best.push(-1); 
    } 

    var answer = findBest(x, cost, capacity, x.length - 1); 
    return answer; 
} 

// Implementation of BestCost function 
var findBest = function(distances, costs, capacity, distanceIndex) 
{ 
    // Return value if it's already have been calculated 
    if (best[distanceIndex] != -1) 
    { 
     return best[distanceIndex]; 
    } 
    // Find cheapest way to fill by iterating on every available gas station 
    var minDistanceIndex = findMinDistance(capacity, distances, distanceIndex); 
    var answer = findBest(distances, costs, capacity, minDistanceIndex) + 
     calculateCost(distances, costs, capacity, minDistanceIndex, distanceIndex); 
    for (var i = minDistanceIndex + 1; i < distanceIndex; i++) 
    { 
     var newAnswer = findBest(distances, costs, capacity, i) + 
     calculateCost(distances, costs, capacity, i, distanceIndex); 
     if (newAnswer < answer) 
     { 
      answer = newAnswer; 
     } 
    } 
    // Save best result 
    best[distanceIndex] = answer; 
    return answer; 
} 

// Implementation of MinGasStation function 
function findMinDistance(capacity, distances, distanceIndex) 
{ 
    for (var i = 0; i < distances.length; i++) 
    { 
     if (distances[distanceIndex] - distances[i] <= capacity) 
     { 
      return i; 
     } 
    } 
} 

// Implementation of Cost function 
function calculateCost(distances, costs, capacity, a, b) 
{ 
    var distance = distances[b] - distances[a]; 
    return costs[b] * (distance/capacity); 
} 

完全可行的html页面，请here