Uma possível abordagem é a seguinte.
Eu vou fazer as seguintes suposições. Deixe-me saber se algum deles está realmente incorreto. Assim que encontrarmos um carro que possa ser adicionado em nenhuma das faixas, paramos de adicionar carros à balsa (não é permitido pular um carro grande para adicionar um carro menor que aparece na lista). Eu vou fazer a suposição de que a soma do comprimento de todos os carros está abaixo de 2d. Se não for o caso, isso pode ser facilmente aplicado em uma etapa de pré-processamento. Eu também vou considerar que d é um valor inteiro, assim como todos os tamanhos de carros.
O que vamos fazer agora é resolver um problema da mochila 0/1 para descobrir se um conjunto de carros pode caber em ambas as pistas.
Aqui o tamanho da mochila é d (na verdade é uma pista), o tamanho dos itens é o tamanho dos carros e o valor associado aos itens é o tamanho dos carros (ou seja, queremos preencher uma pista, tanto quanto possível). Para resolver este problema de mochila 0/1, você pode usar o algoritmo DP descrito na seguinte página da wikipedia: link ( Vou apenas reproduzi-lo aqui para que a resposta apareça mesmo se a página da Wikipedia desaparecer:)
Vamos chamar s1, o tamanho do carro 1, s2 o tamanho do carro2 e assim por diante (vamos considerar que temos n carros).
Defina m [i, s] como o valor máximo que pode ser obtido com um tamanho total usado menor ou igual a s usando carros até i (primeiros carros).
Podemos definir m [i, s] recursivamente da seguinte forma: m [i, s] = m [i-1, s] se si > s \, (o novo carro é maior que o limite de tamanho atual) m [i, s] = max (m [i-1, s], \, m [i-1, s-si] + si) se si menor ou igual a s.
A solução pode então ser encontrada calculando m [n, d].
vamos chamar s, a soma do comprimento dos carros na solução do problema da mochila. Se a soma de todos os comprimentos de carros for menor ou igual a d, então todos os carros considerados para resolver os problemas da mochila podem caber na balsa (sendo uma pista todas as selecionadas para fazer parte da solução da mochila, a outra pista sendo o resto). Se a soma do comprimento do resto dos carros for mais que d, então todos os carros não caberão na balsa. Remova o último carro da lista dos carros e resolva novamente o problema da mochila. Faça isso até que a soma do comprimento dos carros não selecionados esteja abaixo de d.
A complexidade do algoritmo DP para resolver o problema da mochila é O (nd) e precisa ser resolvida no máximo n vezes - > complexidade O (n ^ 2d)
Aqui está um esboço da solução em 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()