Professor Midas drives an automobile from Newark to Reno along Interstate 80. His car’s gas tank, when full, holds enough gas to travel n miles, and his map gives the distances between gas stations on his route. The professor wishes to make as few gas stops as possible along the way. Give an efficient method by which Professor Midas can determine at which gas stations he should stop, and prove that your strategy yields an optimal solution

The GREEDY Algorithm

Explanation:

Based on the situation given in question, the Greedy algorithm shall give the optimal solution to professor

Suppose that the cities are at locations0 =x0< x1< . . . < x

We shall use the induction method to prove that G is the optimal solution valid for numbers less than n

We assume another solution Z which we initially consider to be optimum as well, based on that when Z fills the tank, it fills it to full level

Let us state the values in case of n intervals. Given below, we say that g1 is the first stop and z1 is also the first stop.

This can be written as ;

G=g1, g2, . . . , gk

Z=z1, z2, . . . , zk’

Here k’ <= k and k < n

Let I be an idex where for the first time gi is not equal to zi

Considering t= maxi Zi

Z′=g1, z2, z3, . . . , zk′

Now since z2, z3, . . . , zk′ should be an optimal stopping pattern for the problem otherwise we have chosen Z, with smaller gas filling (not feasible)

Using induction hypothesis we conclude thatg2, . . . , gk is an optimal stopping pattern, which is based on greedy algorithm