Ferry loading problem

I have a difficulty with an undermentioned algorithmic problem:

There is a three-lane ferry in a port and in front of it there is a queue of N vehicles. Each of them has got specified lenght in cm. We also know the lenght (L) of the ferry. We have to propose an algorithm, which enables to load the ferry with the maximum amount of cars from the queue. Each car can choose between taking one of the three lanes: left, center or right. Cars have to be processed in order - for each car (starting from the front) we have to decide on which lane it will drive onto. If there is no enought free space for the car being in the front of the queue 开发者_运维技巧at the moment we finish. Remaining cars wait for the next ferry.

Greedy method (first-fit) isn't the most efficent in every case (e.g. if L is 5 and we have the queue 5 2 2 3 3). Thus I were trying to figure out what is the solution if we will think of it as an dynamic programming problem. Still I'm trying to find any, but all dynamic algorithms I know (especially from the Introduction to Algorithms) seem not to fit that problem.

Thank you in advance for any suggestions. :)

First, notice the similarities between this problem and the knapsack problem, the partition problem, and the bin packing problem.

This suggests a pseudopolynomial time dynamic programming solution. In each of those problems, we kept track of the optimal solution for a knapsack of every size less than the one we're interested in. In this case, our knapsacks are the three lanes. Now I hope the algorithm isn't too far from your mind yet.

I'm not going to give you the complete answer since this is a problem from UVa Online Judge. However I hope this puts you in the right direction. There is a lot of information out there on how to solve knapsack-related problems.