Test 2- 3

Inicialmente se plantean dos opciones Programación Dinámica y Greedy. Debido a que la programación dinámica se basa en el paradigma de divide y vencerás, y como en este problema este no aplica, la estrategia a usar es la de Greedy.

El profesor Midas comienza con tanque lleno, entonces deberia dirigirse a la estacion mas lejana, esta seria la estructura optima del problema. La solucion de recurrencia seria que, el profesor Midas cuando llegue a la estacion mas lejana dentro de las n millas de recorrido, nuevamente cargue el tanque de su automovil, y con esto pueda volver a llegar a la estacion mas lejana desde su ultima parada. El debe verificar si puede llegar a la proxima estacion sin detenerse, es decir el debe observar en que estacion debe hacer su detencion para seguir su recorrido, previniendo de tal manera que no se quede varado a mitad de camino.

Se tiene que existen k estaciones de gas, ahora tenemos que la estructura optima del recorrido del Profesor Midas es detenerse en m estaciones de servicio siendo esta la mas optima solución. Se tiene que la solucion Greedy es tomar la k-esima estacion de gas como la primera parada del automovil, es decir si el decidiera detenerse en una estacion menor a k entonces el Profesor Midas no llegaria tan lejos y tendria que hacer de nuevo una parada mas. Si se tiene que en el mapa entonces se tiene que observar cada estacion del mapa para determinar cual es la ruta mas optima y se tiene que la solucion del problema es de O(m).