Gas Station-like Algorithm with minimum cost? Greedy or DP?

algorithm dynamic-programming greedy
Anagha picture Anagha · Jan 27, 2014 · Viewed 7.5k times · Source

I have an array of n service stations D[] on a highway such that D[i] is the distance of the station i from the start of the highway.

I also have an array of costs C[] such that C[i] is the cost of getting my vehicle serviced at station i.

I have to get my car serviced at the first station, and my car can travel at most 100 miles between stations.

What is the most efficient algorithm to get from the start of the highway to the end with the least cost (I need to know which stations to stop at)? I was able to find a greedy solution for minimizing the number of stops, but for the least cost, I am thinking DP, with the optimal subproblem:

bestcost[j] = min( 0<i<j bestcost[i] + C[j] s.t. D[j]-D[i] <= 100)

and have a separate array last[j] which contains the last station at which to stop, which would be the best i from above subproblem.

Would this be the right approach, or is there a better Greedy / DP solution?

Answer

Antti Huima picture Antti Huima · Jan 27, 2014

The recurrence is better written as

bestcost_serviced_at[j] =
  min(0<i<j: bestcost_serviced_at[i] + C[j] s.t. D[j]-D[i] <= 100)

because the recurrence gives the optimal cost assuming that the vehicle actually stops at station j for service.

Then the solution to the problem is

min (j: bestcost_serviced_at[j] s.t. highway_end - D[j] <= 100)

I don't think a greedy algorithm would work.

Related questions

How is dynamic programming different from greedy algorithms?

In the book I am using Introduction to the Design & Analysis of Algorithms, dynamic programming is said to focus on the Principle of Optimality, "An optimal solution to any instance of an optimization problem is composed of optimal solutions …

Read More
Optimal room count and sizes for N overlapping Meeting Schedules

I bumped into this question and I am not sure if my solution is optimal. Problem Given N weighted (Wi) and possibly overlapping intervals (representing meeting schedules) , find the minimum number "&" capacity of meeting rooms needed to conduct all …

Read More
Given an array of integers, find the LARGEST number using the digits of the array such that it is divisible by 3

E.g.: Array: 4,3,0,1,5 {Assume all digits are >=0. Also each element in array correspond to a digit. i.e. each element on the array is between 0 and 9. } In the above array, the largest number is: 5430 {using digits 5, 4, 3 and 0 from the …

Read More