Bridge Crossing Problem

Problem Statement

Bridge Crossing Problem Problem Description A narrow one-way bridge can support a total load of at most U units at any instant. A queue of N cars is waiting to drive across it. The car standing at position k in the queue weighs weight[k] , for k in the range [0, N-1] ; weight[0] is the car at the head of the queue. The bridge is operated so that at most two cars are on it at the same time , and the cars leave it in the same order in which they entered: the first car in the queue drives onto the bridge; the second car drives on next, so both are on the bridge together; the moment the first car drives off, the third car drives on; the moment the second car drives off, the fourth car drives on; and so on, until the queue is empty. In other words, at every moment during the crossing the bridge carries some car together with the car that is immediately behind it in the queue (the very first and the very last cars are alone on the bridge for a short while). With some queues this schedule wou