This problem deals with determining the bus stops used by an express bus. As an express service it can potentially stop at any of the regular bus stops on the route. Since it is an express service, only a subset of the bus stops available will be used and the aim of the bus stop problem is to decide which bus stops will be used by the express bus. The Public Transport Authority (PTA) has decided that the distance between two bus stops that are serviced by the express service must be strictly larger than K km. In addition, some bus stops near major trac junctions, big public buildings or industrial areas are of course more important than stops in residential areas or in sparsely populated areas. This is handled by the PTA by assigning every bus stop a potential revenue by servicing that given bus stop. Formally the problem is dened by a route of length M km. This includes the starting depot 0 and the ending depot n + 1. A number of bus stopsn is given along the route. Each bus stop i is characterised by the distance 0 di M from the starting depot and its potential revenue ri > 0. We assume that the bus stops are given in order so that d1

Subquestion 2.1

A dynamic programming solution for the problem could be set up in the following way. For each bus stop i we dene ei as the last bus stop where we can stop and still being able to also stop at bus stop i. If none of the bus stops between the depot and bus stop i can be used, we assign ei the value 0. Dene P(i) as the optimal solution for the bus stop problem including bus stops 1,...,i. Therefore by ndingP(n), we have solved the original problem. Starting condition will be P(0) which is equal to 0. The dynamic programming approach will be: P(0) = 0 P(i) = max {P(i1),r i + P(ei)} In order to nd the solution corresponding to the optimal value, we backtrack through the solutions. 3 Explain how the dynamic programming approach described solves the problem.