您和您的朋友正开车去蒂华纳（Tijuana）度假。您为旅行节省了金钱，因此您希望尽量减少旅途中的汽油成本。为了最大程度地减少您的汽油费用，您和您的朋友汇编了以下信息。首先，您的汽车可以使用汽油箱可靠地行驶数英里（但不能再继续行驶）。您的一位朋友从网络上开采了加油站数据，并绘制了沿途的每个加油站以及该加油站的汽油价格。具体来说，他们创建了从最接近到最远的n + 1个加油站价格列表，以及两个相邻的加油站之间的n个距离列表。塔科马是加油站0，蒂华纳是加油站n。为方便起见，他们已将汽油的成本转换为您的汽车行驶每英里的价格。此外，还计算了两个相邻加油站之间的距离（以英里为单位）。您将以满满的汽油开始旅程，到达蒂华纳时，您将准备回程。您需要确定在哪个加油站停车，以最大程度减少旅途中的加油成本。
样本输入：
价格（每英里美分）
[12,14,21,14,17,22,11,16,17,12,30,25,27,24,22,15,24,23,15,21]
距离（英里）
[31,42,31,33,12,34,55,25,34,64,24,13,52,33,23,64,43,25,15]
您的汽车可以用汽油箱行驶170英里。
我的输出：
这次旅行的最低费用是：$ 117.35
加油站停在：[1、6、9、13、17、19]
我已经解决了这个问题，但是我不确定我是否做对了。如果错误的话，有人可以给我一些建议或指向正确的方向吗？先感谢您。
public class GasStation {
/** An array of gas prices.*/
private int[] myPrice;
/** An array of distance between two adjacent gas station.*/
private int[] myDistance;
/** Car's tank capacity.*/
private int myCapacity;
/** List of gas stations to stop at to minimize the cost.*/
private List<Integer> myGasStations;
/**
* A constructor that takes in a price list, distance list, and the car's tank capacity.
* @param thePrice - price list
* @param theDistance - distance list
* @param theCapacity - the car's capacity
*/
public GasStation(final int[] thePrice, final int[] theDistance,
final int theCapacity) {
myPrice = thePrice;
myDistance = theDistance;
myCapacity = theCapacity;
myGasStations = new ArrayList<>();
}
/**
* Calculate for the minimum cost for your trip.
* @return minimum cost
*/
public int calculateMinCost() {
int lenP = myPrice.length;
int lenD = myDistance.length;
if (lenP == 0 || lenD == 0 || myCapacity == 0) return 0;
// gas station -> another gas station (moves)
Map<Integer, Integer> gasD = new HashMap<>();
int[] D = new int[lenD + 1];
D[0] = 0;
// calculate the total distance
for (int i = 0; i < lenD; i++) {
D[i + 1] = D[i] + myDistance[i];
}
int len = D.length;
for (int i = 1; i < len - 1; i++) {
int j = len - 1;
while (D[j] - D[i] >= myCapacity) {
j--;
}
gasD.put(i, j - i);
}
int min = Integer.MAX_VALUE;
for (int i = 1; i < len; i++) {
int temp = 0;
int cur = i;
List<Integer> tempList = new ArrayList<>();
if (D[i] <= myCapacity) {
temp = D[cur] * myPrice[cur];
tempList.add(cur);
int next = gasD.get(cur) + cur;
while (next < len) {
temp += (D[next] - D[cur]) * myPrice[next];
cur = next;
tempList.add(cur);
if (gasD.containsKey(cur)) next = gasD.get(cur) + cur;
else break;
}
if (temp < min) {
min = temp;
myGasStations = tempList;
}
}
}
return min;
}
/**
* Get gas stations to stop at.
* @return a list of gas stations to stop at
*/
public List<Integer> getGasStations() {
return myGasStations;
}
}
最佳答案
设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处加油，因此我们应该仅在1至18站（即cost[1], cost[2], .., cost[18]）计算加油的费用。完成此操作后，问题的答案将是MIN { cost[14], cost[15], cost[16], cost[17], cost[18] }，因为距station 19 170英里以内的唯一站点是14,15,16,17,18站点，因此我们可以通过在这5个站点中的一个进行重新填充来到达19站点。
在使用基本案例定义了上述递归关系后，可以按以下方式将其转换为循环：
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];
}