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

Question

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?

Tropo

I don't see a greedy solution. The DP recurrence is correct. You can get runtime O(n) with a monotonic queue that allows you to find the min in O(1), which is optimal and also has a low constant factor. That even works if the range of your bike is not constant. – Tillion

@NiklasB. actually his solution is greedy, at each stop he will look for the best option using only the cost .. his solution works fine, except it is not optimal, since he is not considering how much gas exist at every distance and how much can he re-fill with that price make the issue here more complex, and makes a cheaper price-per-gas-unit isn't always the best option to make a stop – Conte

@KhaledAKhunaifer please read my question carefully, I am not considering how much gas exists, because this is not the gas station problem, but a variation. It's a service station problem where I have to make a fixed expense C[i] every time I stop at a given station i. – Tropo

@Tropo as Niklas B. mentions, you can go backward from the end station, every time go through each station, update the min cost to reach end station from this station. I don't see any greedy here. – Gilreath

@Tropo I see, but here is the worst case to your greedy solution .. imagine that the gas-stations have ascending costs C[i] > C[j] where i > j, this is where you will stop at every station on the road – Conte

@KhaledAKhunaifer dude, read the question. The greedy algorithm OP mentioned doesn't even consider costs – Tillion

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

@Khaled: Either one of us must be missing something: "I was able to find a greedy solution for minimizing the number of stops, but for the least cost, I am thinking DP" Are you talking about the DP solution? Because that one is provably correct (it's pretty easy to prove) – Tillion

There is a fixed servicing cost per station i that you either pay (in which case your gas is filled and you pay C[i]) or you don't (in which case your gas is not filled and you pay 0). – Tillion

@NiklasB. I thought he came up with a good algorithm, but his solution was a greedy one, where at every stop, he look at the stations that are within 100Km from there and choose the one that has the lowest cost, then from that chosen station he recur .. if he is trying to minimize total cost, that algorithm is the worst, because in my scenario he is going to pay the total cost of all stations – Conte

@Khaled: Sorry, I think you don't understand the algorithm. bestcost[i] is the minimal cost to arrive at D[i] AND have a service at station i. Obviously you HAVE to pay C[i] if you decide to do that. But that doesn't mean that this subresult is ever used, so in particular it does NOT mean that we use the station in a globally optimal solution. Do you have experience with dynamic programming? – Tillion

@NiklasB. The problem I see is that if you apply bestcost[j] = min( 0<i<j bestcost[i] + C[j] s.t. D[j]-D[i] <= 100) starting from station 0 .. you have one path, it's linear and deterministic, the operation min(bestcost[i]+C[j]) is equivalent to min(C[j]) – Conte

@Khaled: j is constant if you compute bestcost[j], so min(C[j]) does make no sense at all. "the operation min(bestcost[i]+C[j]) is equivalent to min(C[j])" ist just wrong, you iterate over the array bestcost[j] for the reachable stations and take the minimum, then you add C[j] because you decided to stop at j. "you have one path, it's linear and deterministic" Well the resulting path could look like this: Stop at station 1, skip station 2, skip station 3, stop at 4, stop at 5, skip 6, stop at 7. What do you mean by "linear and deterministic"? – Tillion

@Khaled: Here is an example implementation, maybe that helps convince you: ideone.com/gm5eit – Tillion

@NiklasB. nice one, that's dynamic programming. but that algorithm you wrote yourself, not the one we see at the question. – Conte

@KhaledAKhunaifer: Yes it is. Look closely. Lines 14 to 24 implement OP's exact recurrence. bestcost[j] = min(0<i<j bestcost[i] + C[j] s.t. D[j]-D[i] <= 100) If you can't see that, I have to doubt your ability to read code... – Tillion

Answer 1

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.

Epochal

Answer 2

I think your DP is bit incomplete, here is a DP recurrence which is more comprehensive :-

if(highway_end-D[i]>100) {

   minCost[i] = min(0<i<j && D[j]-D[i] <= 100 : minCost[j]+C[i])
} 

else  minCost[i]  = C[i]     

minCost[i] = minimum cost to reach destination if you have filled up at i

Sort the stations according to distance from start and use DP in higher to lower stations distances. Use sorted array to find nearer neighboring stations <=100 miles away.

Edit : -

Can be done in O(NlogN) using min heap.

Carrie

Can be implemented in O(n) though if distances are pre-sorted – Tillion

@NiklasB. even if it is presorted how to satisfy D[j]-D[i]<=100 and min(minCost[j]) in O(1) for each subproblem ? – Carrie

a segment tree gives you O(log n) per transition. As I mentioned, a monotonic queue with a sliding window algorithm even allows for constant time transitions. I'll write an answer later. – Tillion

See my answer for a simple O(n) algo to solve the recurrence, in case you're interested – Tillion