Marathon

A dynamic programming solution to help Boston Marathon runners Marathon runners carry water to keep them hydrated as they run. But carrying too much water decreases their performance because of the weight they have to carry. So each runner chooses an appropriate size water bottle that will last for a certain number of miles before he or she has to stop to fill up. Because stopping increases their total running time, they want to stop as few times as possible. The marathon organizers have water available at n pre-determined locations along the route. They want you to build an app that, when the runner inputs m, the number of miles he or she can run before having to stop, uses the water locations along the route to determine the minimum number of stops the runner has to make, and provides that information as he or she nears each selected water location. So you have to come with an algorithm that, given the distance from a starting location to the first water location, the distance between all intermediate water locations, and the distance between the last water location before finish line and the finish line, will compute the locations to stop at so that the runner makes the minimum number of stops.

1. Come up with a recursive characterization of the solution. Then explain why it has optimal substructure. Both these should be included in your submission.
2. Design a corresponding non-recursive bottom-up table lookup algorithm to solve the problem. This should be included in your submission.
3. Do an approximate analysis of the efficiency of your algorithm. This should be included in your submission.
4. Implement your algorithm in a program. It should read an input text file named input.txt formatted as follows: (a) The first line contains the integer m. (b) The second line contains the integer n. (c) The third line contains n+1 integers separated by a blank space that are distances: the first integer is the distance in miles between the starting point and the first water location, the second integer is the distance between the first and the second water locations, the third integer is the distance between the second and third water locations,…the n-th integer is the distance between the (n-1)-th and n-th water locations, and the last integer is the distance between the final water location and the destination. Your program should output a text file formatted as follows: (a) The first line should contain the minimum number of stops needed, as determined by your algorithm. (b) The second line should contain k integers, which are the ids of the selected water locations, 1<=k<=n.