You wish to drive from Miami to Gainesville along I-75 minimizing the time that

Question

You wish to drive from Miami to Gainesville along I-75 minimizing the time that you are stopped for gas. You are told beforehand the capacity C of you gas tank in liters, your rate F of fuel consumption in liters/kilometer, the rate R in liters/minute at which you can fill your tank at a gas station. Let d1 < d2 <…< dn be the locations of all the gas stations along the route where di is the distance from Miami to the gas station. So if you stop to fill your tank from 2 liters to 8 liters, you would have to stop for 6/R minutes. Give a correct greedy algorithm for this problem, and give an efficient implementation.

Explanation / Answer

fill the tank full at any gas station if C/F < remaining distance or fill the tank upto F*remaining distance

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.