Question

16.2 #4) Please answer full question thoroughly showing detailed work. SUBMIT ORIGINAL (not book solutions) work and ensure it is correct for thumbs up. If work is NOT ORIGINAL will give THUMBS DOWN!!!

Professor Gekko has always dreamed of inline skating across North Dakota. He plans to cross the state on highway U.S. 2, which runs from Grand Forks, on the eastern border with Minnesota, to Williston, near the western border with Montana. The professor can carry two liters of water, and he can skate m miles before running out of water. (Because North Dakota is relatively flat, the professor does not have to worry about drinking water at a greater rate on uphill sections than on flat or downhill sections.) The professor will start in Grand Forks with two full liters of water. His official North Dakota state map shows all the places along U.S. 2 at which he can refill his water and the distances between these locations. The professor’s goal is to minimize the number of water stops along his route across the state. Give an efficient method by which he can determine which water stops he should make. Prove that your strategy yields an optimal solution, and give its running time.

Answer 1

Greedy method is the best method for Professor. Westernmost place is where He must go he can easily refill his bottles from the distance of m miles of the first starting point. What he can do is to determine a point where he can cover maximum distance then there must be a way at which he can refill before it runs out. Now we know that the first path is way to Grand Forks so we have chosen the first stopping point pm we have solve at part of problem our beginning point is p. We can assume that O is an optimal solution and these are the first stopping points o1,o2,o3,o4...…on. We can assume that f1 is the furthest stopping point so by this we can deduce that o2-01

IF YOU HAVE ANY QUERY PLEASE COMMENT DOWN BELOW

PLEASE GIVE A THUMBS UP