You are saving your money for the trip and so you want to minimize the cost of g

ID: 3866867 • Letter: Y

Question

You are saving your money for the trip and so you want to minimize the cost of gas on the wav. In order to minimize your gas costs you and your friends have compiled 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. State a self-reduction for your problem. State a dynamic programming algorithm based off of your self reduction that computes the minimum gas cost. Design a function that recovers the gas stations that should be stopped at to achieve the minimum cost. Use your algorithm to compute minimum cost and the right gas stations for the following lists of gas stations, distances and gas tank capacity. Design a function that recovers the gas stations that should be stopped at to achieve the minimum cost. Use your algorithm to compute minimum cost and the right gas stations for the following lists of gas stations, distances and gas tank capacity. Prices (cents per mile) [15, 24, 27, 14, 21, 22, 24, 16, 17, 12, 11, 25, 17, 12, 22, 15, 30, 23, 14, 21] Distances (miles) [64, 42, 25, 33, 12, 34, 55, 25, 31, 64, 24, 13, 52, 31, 23, 34, 43, 33, 15] Your car can travel 164 miles on a tank of gas.

Explanation / Answer

As per problem statement greedy approach works: Start your trip from Tacoma with a full tank. since the gas stations on the current path may be more expensive that stations slightly off the shortest path. We fill the tank with less price gas station and back to the target path.

For this sitaution, Greedy algorithm is most suitable to find the minimum cost.

int minimumCost(int cost[][N], int source, int destination)

{

if (source == destination || source+1 == destination)

{

return source[s][destination];

}

int min = cost[source][destination];

for (int i = source+1; i<destination; i++)

{

int c = minimumCost(cost, source, i) +

minimumCost(cost, i, destination);

if (c < min)

min = c;

}

return min;

}

Let starting station as 0 and last station before we reach to Tijuana N-1.

minimumCost(0, N-1) = MIN { cost[0][n-1],
cost[0][1] + minCost(1, N-1),
minCost(0, 2) + minCost(2, N-1),
........,
minCost(0, N-2) + cost[N-2][n-1] }

Here cost[i][j] indicates cost to reach j from i.