Hi,

I recently encountered a problem in my algorithms class. The problem is as follows:

"You are driving a bus along a highway, full of rowdy, hyper, thirsty students and a soda fountain machine. Each minute that a student is on your bus, that student drinks one ounce of soda. Your goal is to drop the students o quickly, so that the total amount of soda consumed by all students is as small as possible. You know how many students will get o of the bus at each exit. Your bus begins somewhere along the highway (probably not at either end) and moves at a constant speed. You must drive the bus along the highway; however, you may drive forward to one exit then backward to an exit in the opposite direction, switching as often as you like. (You can stop the bus, drop o students, and turn around instantaneously.) The bus travels at constant speed.

Describe an efficient algorithm to drop the students o so that they drink as little soda as possible. Input consists of bus route (a list of exits, together with travel time between successive exits), the number of students you will drop off at each exit, and the current location of your bus(which is also an exit)."

Initially, I was thinking of a greedy strategy to choose the exit at minimum distance from my current location (choose one with maximum drop-off capacity if more than one exits), and then continue from the new location. However, this does not result in optimal solution.

Can anyone give a hint for the expected DP solution over here ?

Thanks.