Gas Station Dynamic Programming

Question

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;
}

}

Answer 1

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];
}