Ferry Loading Problem

Overview

We consider the case of a ferry that transports cars across a river. The ferry comprises two lanes of cars throughout its length. Before boarding on the ferry, the cars wait on a single queue in their order of arrival. When boarding, each car can go to either the left or the right lane. Boarding stops when the next car in the queue does not fit in the space left in either lane.

Given the length LIN of the ferry and the lengths liIN of all cars i0 in the queue, what is the maximum number of cars that can be loaded onto the ferry?

Note 1: The total number of boarded cars and the length of the right lane (k,len) can be used to characterize an intermediate configuration.

Note 2: Given a state (k,len), two possibilities exist for the next car to board: (k+1,len+lk+1) if the car is added to the right lane or (k+1,len) if the car is added to the left lane.

Implementation

Create a class Ferry.java to implement an efficient solution to this problem using a hashing table. Your program should obtain the value of the constant L as an argument, and using StdIn.java import the car information in the following format.

The first line contains the number n of car lengths values to read. It is followed by a list of n integers l0, l1, ..., ln1, one per line, each corresponding to the length of a car in the queue. Your program must print out to standard output the maximum number of cars that can be loaded on the ferry.