加油站动态规划

Question

您和您的朋友正开车前往蒂华纳度春假。您正在为旅行省钱，因此您希望尽量减少途中的汽油费用。为了最大限度地减少您的天然气成本，您和您的朋友整理了以下信息。首先，您的汽车可以通过一箱油可靠地行驶 m 英里（但不能再远）。您的一位朋友从网上挖掘了加油站数据，并绘制了您路线上的每个加油站以及该加油站的汽油价格。具体来说，他们创建了一个从最近到最远的 n+1 个加油站价格列表以及两个相邻加油站之间的 n 个距离的列表。塔科马是 0 号加油站，蒂华纳是 n 号加油站。为了方便起见，他们将汽油成本转换为汽车行驶每英里的价格。此外，还计算了两个相邻加油站之间的英里距离。您将在加满油的情况下开始您的旅程，当您到达蒂华纳时，您将\xef\xac\x81ll 准备回程。您需要确定在哪些加油站停车，以最大限度地减少旅途中的汽油成本。

\n\n

输入示例：

\n\n

价格（每英里美分）\n[12,14,21,14,17,22,11,16,17,12,30,25,27,24,22,15,24,23,15,21]

\n\n

距离（英里）\n[31,42,31,33,12,34,55,25,34,64,24,13,52,33,23,64,43,25,15]

\n\n

您的汽车加一箱油可以行驶 170 英里。

\n\n

我的输出：

\n\n

此次旅行的最低费用为： $117.35

\n\n

加油站停靠：[1, 6, 9, 13, 17, 19]

\n\n

我已经解决了这个问题，但我不确定我是否以正确的方式完成了它。如果错误的话，有人可以给我一些建议或指出正确的方向吗？先感谢您。

\n\n

public class GasStation {\n\n/** An array of gas prices.*/\nprivate int[] myPrice;\n/** An array of distance between two adjacent gas station.*/\nprivate int[] myDistance;\n/** Car's tank capacity.*/\nprivate int myCapacity;\n/** List of gas stations to stop at to minimize the cost.*/\nprivate List<Integer> myGasStations;\n\n\n/**\n * A constructor that takes in a price list, distance list, and the car's tank capacity.\n * @param thePrice - price list\n * @param theDistance - distance list\n * @param theCapacity - the car's capacity\n */\npublic GasStation(final int[] thePrice, final int[] theDistance,\n        final int theCapacity) {\n    myPrice = thePrice;\n    myDistance = theDistance;\n    myCapacity = theCapacity;\n    myGasStations = new ArrayList<>();\n}\n\n\n/**\n * Calculate for the minimum cost for your trip.\n * @return minimum cost\n */\npublic int calculateMinCost() {\n\n    int lenP = myPrice.length;\n    int lenD = myDistance.length;\n    if (lenP == 0 || lenD == 0 || myCapacity == 0) return 0;\n\n    // gas station -> another gas station (moves) \n    Map<Integer, Integer> gasD = new HashMap<>();\n    int[] D = new int[lenD + 1];\n    D[0] = 0;\n\n    // calculate the total distance \n    for (int i = 0; i < lenD; i++) {\n        D[i + 1] = D[i] + myDistance[i];\n    }\n\n    int len = D.length;\n    for (int i = 1; i < len - 1; i++) {\n        int j = len - 1;\n        while (D[j] - D[i] >= myCapacity) {\n            j--;\n        }\n        gasD.put(i, j - i);\n    }\n\n    int min = Integer.MAX_VALUE;\n\n    for (int i = 1; i < len; i++) {\n        int temp = 0;\n        int cur = i;\n        List<Integer> tempList = new ArrayList<>();\n        if (D[i] <= myCapacity) {\n            temp = D[cur] * myPrice[cur];\n            tempList.add(cur);\n            int next = gasD.get(cur) + cur;\n            while (next < len) {\n                temp += (D[next] - D[cur]) * myPrice[next];\n                cur = next;\n                tempList.add(cur);\n                if (gasD.containsKey(cur)) next = gasD.get(cur) + cur;\n                else break;\n            }\n\n            if (temp < min) {\n                min = temp;\n                myGasStations = tempList;\n            }\n\n        }\n    }\n\n\n    return min;\n}\n\n/**\n * Get gas stations to stop at.\n * @return a list of gas stations to stop at\n */\npublic List<Integer> getGasStations() {\n    return myGasStations;\n}\n

\n\n

}

\n

Answer 1

让重新填充的最小成本station i表示为cost[i]

给定问题陈述，如何表达该成本？我们知道，每次重新填充都必须在上次重新填充之后
完成， 因此最小成本可以表示如下： 170 miles

cost[i] = MIN { cost[j] + price[i] * distance_from_i_to_j } for every j such that distance(i,j) <= 170 mi

cost[0] = 0如果我们不考虑 处的满罐成本，则为基本情况station 0，否则基本情况为cost[0]= 170 * price[0]

我假设我们不考虑 处的满箱成本station 0，并且在最后一点不需要重新填充，即station 19

通过查看上面定义的递归关系，我们可以很容易地注意到同一子问题被多次调用，这意味着我们可以利用动态规划解决方案来避免可能的指数运行时间。

另请注意，由于我们不需要在 处加气，因此我们应该仅通过即 来station 19计算在车站加气的成本。这样做之后，问题的答案将是，因为距离 170 英里以内的车站只有一个，所以我们可以通过这 5 个车站中的一个加油站来到达车站。 118cost[1], cost[2], .., cost[18]MIN { cost[14], cost[15], cost[16], cost[17], cost[18] }station 1914,15,16,17,1819

当我们定义了上述与基本情况的递归关系后，我们可以通过以下方式将其转换为循环：

int price[] =  {12,14,21,14,17,22,11,16,17,12,30,25,27,24,22,15,24,23,15,21}; //total 20 stations

int distance[] = {31,42,31,33,12,34,55,25,34,64,24,13,52,33,23,64,43,25,15};  //total 19 distances      

int N=19;
int[] cost = new int[N];    
int[] parent = new int[N]; //for backtracking

cost[0] = 0; //base case (assume that we don't need to fill gas on station 0)

int i,j,dist;
int maxroad = 170;

for(i=0; i<N; i++) //initialize backtracking array
    parent[i] = -1;


for(i=1; i<=N-1; i++) //for every station from 1 to 18
{

        int priceval = price[i]; //get price of station i               
        int min = Integer.MAX_VALUE;                
        dist = 0;            

        for(j=i-1; j>=0; j--) //for every station j within 170 away from station i
        {   
            dist += distance[j]; //distance[j] is distance from station j to station j+1
            if(dist>maxroad)
               break;   

            if((cost[j] + priceval*dist)<min) //pick MIN value defined in recurrence relation                       
               {
                min = cost[j] + priceval*dist;
                parent[i] = j;
               }

        }

        cost[i] = min;              

}


//after all costs from cost[1] up to cost[18] are found, we pick
//minimum cost among the stations within 170 miles away from station 19
//and show the stations we stopped at by backtracking from end to start

int startback=N-1;
int answer=Integer.MAX_VALUE;
i=N-1;
dist=distance[i];
while(dist<=maxroad && i>=0)
{
   if(cost[i]<answer)
      {
       answer = cost[i];
       startback=i;
      }  
   i--;
   dist += distance[i];
}


System.out.println("minimal cost=" + answer + "\nbacktrack:");

i=startback;
while(i>-1) //backtrack
{
    System.out.println(i + " ");
    i = parent[i];
}