Geek Answers Handbook

A gas station-like algorithm with minimal cost? Greedy or DP?

I have an array of service stations n D[] on the highway, so D[i] is the distance of station i from the beginning of the highway.

I also have an array of costs C[] , so C[i] is the cost of shipping my car to station i.

I need my car to be serviced at the first station, and my car can travel no more than 100 miles between stations.

What is the most efficient algorithm that can be obtained from the beginning of the highway to the end at the lowest cost (I need to know which stations to stop at)? I was able to find a greedy solution to minimize the number of stops, but at the lowest price, I think DP with the optimal subtask:

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

and have a separate array last[j] , which contains the last station at which it stops, which would be the best i from the above subtask.

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

+6
source share
2 answers

Repetition is better written as

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

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

Then the solution to the problem

 min (j: bestcost_serviced_at[j] st highway_end - D[j] <= 100)

I do not think that the greedy algorithm will work.

+1
source

I think your DP is a little incomplete, here is a DP repetition that is more complete: -

 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 the distance from the beginning and use DP at higher distances to the stations. Use the sorted array to find the nearest nearby stations <= 100 miles.

Edit: -

Can be done in O(NlogN) using a mini-heap.

0
source

More articles:


All Articles