加油站动态编程 [英] Gas Station Dynamic Programming
问题描述
您和您的朋友正开车去蒂华纳(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]
我已经解决了问题，但是我不确定我是否做对了.如果错误，有人可以给我一些建议或指向正确的方向吗?预先谢谢你.
公共类GasStation {/**各种汽油价格.*/private int [] myPrice;/**两个相邻加油站之间的距离数组.*/private int [] myDistance;/**汽车的油箱容量*/private int myCapacity；/**加油站清单，以减少成本.*/私有列表< Integer>myGasStations；/***接受价格表，距离表和汽车油箱容量的构造函数.* @param thePrice-价格表* @param theDistance-距离列表* @param theCapacity-汽车的容量*/公共加油站(final int [] thePrice，final int [] theDistance，最后的int能力){myPrice =价格；myDistance = theDistance；myCapacity =容量；myGasStations = new ArrayList<>();}/***计算旅行的最低费用.* @返回最低费用*/公共诠释calculateMinCost(){int lenP = myPrice.length;int lenD = myDistance.length;if(lenP == 0 || lenD == 0 || myCapacity == 0)返回0;//加油站->另一个加油站(移动)Map< Integer，Integer>gasD = new HashMap<>();int [] D =新的int [lenD + 1];D [0] = 0；//计算总距离for(int i = 0; i< lenD; i ++){D [i + 1] = D [i] + myDistance [i];}int len = D.length;对于(int i = 1; i< len-1; i ++){int j = len-1;而(D [j]-D [i]> = myCapacity){j--;}gasD.put(i，j-i);}int min = Integer.MAX_VALUE;为(int i = 1; i< len; i ++){int temp = 0;int cur = i;List< Integer>tempList = new ArrayList<>();如果(D [i]< = myCapacity){temp = D [cur] * myPrice [cur];tempList.add(cur);int next = gasD.get(cur)+ cur;而(下一个len){temp + =(D [next]-D [cur])* myPrice [next];cur =下一个；tempList.add(cur);如果(gasD.containsKey(cur))next = gasD.get(cur)+ cur;否则休息；}如果(温度<分钟){min = temp;myGasStations = tempList;}}}返回最小值；}/***让加油站停下来.* @返回加油站清单，以停靠*/公共列表< Integer>getGasStations(){返回myGasStations；} }
让 station i 的最小充值成本表示为 cost [i]
鉴于问题陈述，该费用如何表示?
我们知道，每次下一次填充都必须在距离最后一次填充
170英里内完成，
因此最低费用可以表示为:
cost [i] = MIN {cost [j] + price [i] * distance_from_i_to_j}对于每个j，使得距离(i，j)<= 170 mi
基本情况为 cost [0] = 0 的情况下，如果我们不考虑在 station 0 处的满罐费用，则基本情况为 cost [0] = 170 *价格[0]
我将假设我们不考虑在第0站处的满罐成本，并且在最后一点即第19站 时不需要补充燃料>
通过查看上面定义的递归关系，我们可以很容易地注意到同一子问题被多次调用，这意味着我们可以利用动态编程解决方案来避免可能的指数运行时间.
还请注意，由于我们不需要在第19站进行加油，因此我们应该计算在 1 到 18 ，即 cost [1]，cost [2]，..，cost [18] .完成此操作后，问题的答案将是 MIN {cost [14]，cost [15]，cost [16]，cost [17]，cost [18]} 14,15,16,17,18 距离 19站 170英里以内，因此我们可以通过一次加油来到达 19 站在这5个电台中.
在定义了上述具有基本情况的递归关系之后，我们可以通过以下方式将其转换为循环:
int price [] = {12,14,21,14,17,22,11,16,17,12,30,25,27,24,22,15,24,23,15，21};//总共20个电台int distance [] = {31,42,31,33,12,34,55,25,34,64,24,13,52,33,23,64,43,25,15};//总共19个距离int N = 19;int [] cost = new int [N];int []父=新的int [N];//用于回溯cost [0] = 0;//基本情况(假设我们不需要在站点0处加气)int i，j，dist;int maxroad = 170;for(i = 0; i< N; i ++)//初始化回溯数组parent [i] = -1;for(i = 1; i< = N-1; i ++)//对于从1到18的每个电台{int priceval =价格[i];//获取第i站的价格int min = Integer.MAX_VALUE;dist = 0;for(j = i-1; j> = 0; j--)//对于距站点i 170内的每个站点j{dist + =距离[j];//distance [j]是从站点j到站点j + 1的距离如果(dist&maxroad)休息;if((cost [j] + priceval * dist)< min)//选择递归关系中定义的MIN值{最小值=费用[j] + priceval * dist;parent [i] = j;}}成本[i] =最低；}//找到从成本[1]到成本[18]的所有成本后，我们选择//距离19号车站170英里以内的车站中的最低成本//并通过从头到尾的回溯来显示我们停靠的站点int startback = N-1;int answer = Integer.MAX_VALUE;i = N-1；dist = distance [i];while(dist&= maxroad& i&= 0){if(cost [i]< answer){答案=成本[i];startback = i;}一世 - ;dist + =距离[i];}System.out.println("minimum cost =" + answer +"\ nbacktrack:");i = startback;while(i> -1)//回溯{System.out.println(i +");i =父母[i];} You and your friends are driving to Tijuana for springbreak. You are saving your money for the trip and so you want to minimize the cost of gas on the way. In order to minimize your gas costs you and your friends have compiled the following information. First your car can reliably travel m miles on a tank of gas (but no further). One of your friends has mined gas-station data off the web and has plotted every gas station along your route along with the price of gas at that gas station. Specifically they have created a list of n+1 gas station prices from closest to furthest and a list of n distances between two adjacent gas stations. Tacoma is gas station number 0 and Tijuana is gas station number n. For convenience they have converted the cost of gas into price per mile traveled in your car. In addition the distance in miles between two adjacent gas-stations has also been calculated. You will begin your journey with a full tank of gas and when you get to Tijuana you will fill up for the return trip. You need to determine which gas stations to stop at to minimize the cost of gas on your trip.
Sample Input:
Prices (cents per mile) [12,14,21,14,17,22,11,16,17,12,30,25,27,24,22,15,24,23,15,21]
Distances (miles) [31,42,31,33,12,34,55,25,34,64,24,13,52,33,23,64,43,25,15]
Your car can travel 170 miles on a tank of gas.
My Output:
Minimun cost for the trip is: $117.35
Gas stations to stop at: [1, 6, 9, 13, 17, 19]
I have already solved the problem, but I am not sure if I have done it the right way. Would someone please give me some suggestion or point me to a right direction if it is wrong? Thank you in advance.
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;
}
}
Let the minimal cost of refill at station i be denoted as cost[i]
Given the problem statement, how can this cost be expressed?
We know that every next refill has to be done within 170 miles away from the last refill,
so the minimal cost could be expressed as follows:
cost[i] = MIN { cost[j] + price[i] * distance_from_i_to_j } for every j such that distance(i,j) <= 170 mi
with base case cost[0] = 0 if we don't consider the full tank cost at station 0, otherwise the base case is cost[0]= 170 * price[0]
I will assume that we don't consider the full tank cost at station 0, and that there is no refill needed at the final point i.e. station 19
By looking at the recurrence relation defined above, we may easily notice that the same subproblem is called more than once which means that we may utilize dynamic programming solution in order to avoid possibly exponential running time.
Also note that since we don't need to refill at station 19, we should calculate the costs of refilling at stations 1 through 18 only, i.e. cost[1], cost[2], .., cost[18]. After doing that, the answer to the problem would be MIN { cost[14], cost[15], cost[16], cost[17], cost[18] } because the only stations located within 170 miles away from station 19 are stations 14,15,16,17,18 so we may reach station 19 by refilling at one out of these 5 stations.
After we have defined the above recurrence relation with base case, we may convert it into the loop in the following way:
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];
}
这篇关于加油站动态编程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
