2Prove that your greedy criterion does lead to an optimal so

2.Prove that your greedy criterion does lead to an optimal solution.

3.Explain in at most two sentences why your greedy criterion leads to an algorithm that takes O(n) time.

Donald Trump wants to drive his car from point A to point B. When the tank of the car is full, he can drive up to distance D (at the beginning of the trip, the tank is full). During his trip, he will cross n gaz stations where he can fill the tank of his car (the n-th gaz station being at B). Let di (1 S is n) be the distance between the (i -1)-th and the i-th gaz station. We denote by di the distance between A and the first gaz station, and by dn the distance between the (n 1)-th gaz station and the n-th gaz station at B do We suppose that di S D for all 1 SiS n. Donald wants to minimize the number of stops he needs to make. He knows the location of all gaz stations before leaving from A.

Solution

given:

d1+d2+........+dn=D

every d distance ending has a gas station i ( 1 to n)

every di<=D

1) if(di<D)

{ // if d1<D so add d1+d2<D continue to add until the distances becoming larger than D

increment one distance

}

else // di>=D

fill the petrol

thats how the min stopage will take place and surely will lead to lesser no of stops

2) as by taking the shortest route

unless and until

di<D the d\'s are getting added uptil they are >D

so surely lesser no of stopage and petrol filling

hence optimal solution

eg: assume d1+d2=D // 1st stopage

d3+d4+d5=D // 2nd stopage

d6+...........+dn-1=D // 3rd stopage

dn=D // 4th stopage

conclude for di distance only 4 stopage wth this logic

3) it is the greedy sol cause given

di<=D and at every di ending point has a petrol filling tank (1<i<n)

as the user taking shorter distance unless di<D the di\'s being added less no of stopage automatically