A possible approach is the following.
I am going to make the following assumptions. Let me know if either of them is actually incorrect. As soon as we encounter a car that can be added in neither of the lanes, then we stop adding cars to the ferry (it is not allowed to skip a big car to add a smaller car that comes latter in the list). I am going to make the assumption that the sum of the length of all cars is below 2d. If it is not the case, this can easily be enforced in a preprocessing step. I am also going to consider that d is an integer value, as well as all car sizes.
What we are now going to do is solve a 0/1 knapsack problem to find if a set of car can fit in both lanes.
Here the size of the knapsack is d (it is actually a lane), the size of the items are the size of the cars and the value associated with the items are the size of the cars (ie, we want to fill one lane as much as possible). To solve this 0/1 knapsack problem you can use the DP algorithm outlined on the following wikipedia webpage: http://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem (I am just going to reproduce it here so that the answer stands even if the wikipedia page would disappear):
Let us call s1, the size of car 1, s2 the size of car2, and so on (we are going to consider that we have n cars).
Define m[i,s] to be the maximum value that can be attained with a total size used less than or equal to s using cars up to i (first i cars).
We can define m[i,s] recursively as follows:
m[i,s]=m[i-1,s] if si > s\, (the new car is longer than the current size limit)
m[i,s]=max(m[i-1,s],\,m[i-1,s-si]+si) if si less or equal than s.
The solution can then be found by calculating m[n,d].
let us call s, the sum of the length of the cars in the solution from the knapsack problem. If the sum of all the cars length - s is less or equal than d, then all the cars considered for solving the knapsack problems can fit in the ferry (one lane being all those selected to be part of the knapsack solution, the other lane being the rest). If the sum of the length of the rest of the cars is more than d, then all the cars cannot fit in the ferry. Remove the last car from the list of the cars, and solve again the knapsack problem. Do this until the sum of the length of the not selected cars is below d.
The complexity of the DP algorithm to solve the knapsack problem is O(nd) and it needs to be solved at most n times -> complexity O(n^2d)
Here is a sketch of the solution in python:
def solveKnapsack(cars, lengthOfLane):
m = [[0] * (lengthOfLane+1)]
for s in cars:
m.append([])
for j in range(lengthOfLane+1):
if s <= j:
m[-1].append(max(m[-2][j],m[-2][j-s]+s))
else:
m[-1].append(m[-2][j])
return max(m[-1])
def solveTwoLanes(cars, lengthOfLane):
maxOneLane = solveKnapsack(cars, lengthOfLane)
if sum(cars) - maxOneLane <= lengthOfLane:
return len(cars)
else:
return solveTwoLanes(cars[:-1], lengthOfLane)
def main():
# small example that should output 2.
print solveTwoLanes([3,3,3,1],5)
if __name__ =='__main__':main()
