next up previous

CSE 5311 Fall 1999

Quiz #5

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 \(s_1, \ldots, s_g\) 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 d(s1), and $0 < d(s_i) \leq n$ 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.