让最小的补充成本为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] }
因为唯一的车站位于 170 英里以内station 19
是站14,15,16,17,18
这样我们就可以到达车站19
在这 5 个加油站之一进行加油。
当我们定义了上述与基本情况的递归关系后,我们可以通过以下方式将其转换为循环:
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];
}