CSE 5311 Fall 1999
- Professor Midas drives an automobile between two cities m miles apart
along an interstate highway. His car can go n miles on a tank of gas, and he
starts with a full tank. His map indicates that there are g gas stations
along the way, and d(si) is the distance of station ifrom the previous station si-1. The distance to the first gas station is
for all i. The professor wishes to minimize
the number of gas stops during the trip.
- (8 points.)
Prove that this road-trip problem exhibits optimal substructure.
- (12 points.)
Describe a greedy algorithm for solving the road-trip problem and
prove that your algorithm yields an optimal solution.