Un possibile approccio è il seguente.
Farò le seguenti ipotesi. Fammi sapere se uno di questi è effettivamente errato. Non appena incontriamo un'auto che può essere aggiunta in nessuna delle corsie, allora smettiamo di aggiungere auto al traghetto (non è permesso saltare una macchina grande per aggiungere un'auto più piccola che viene da quest'ultima nella lista). Farò l'ipotesi che la somma della lunghezza di tutte le auto sia inferiore a 2d. Se non è il caso, questo può essere facilmente applicato in una fase di pre-elaborazione. Inoltre considererò che d è un valore intero, così come tutte le taglie di auto.
Quello che faremo ora è risolvere un problema dello zaino 0/1 per scoprire se un set di auto può essere inserito in entrambe le corsie.
Qui la dimensione dello zaino è d (è in realtà una corsia), la dimensione degli oggetti è la dimensione delle auto e il valore associato agli oggetti è la dimensione delle auto (cioè, vogliamo riempire una corsia il più possibile). Per risolvere questo problema dello zaino 0/1 è possibile utilizzare l'algoritmo DP descritto nella seguente pagina web di wikipedia: collegamento ( Ho intenzione di riprodurlo qui in modo che la risposta sia valida anche se la pagina di wikipedia scompare):
Chiamiamo s1, la dimensione della macchina 1, s2 la dimensione di car2, e così via (stiamo considerando che abbiamo n auto).
Definisci m [i, s] come il valore massimo che può essere raggiunto con una dimensione totale usata minore o uguale a s utilizzando auto fino a i (prime vetture).
Possiamo definire m [i, s] ricorsivamente come segue:
m [i, s] = m [i-1, s] se si > s \, (la nuova auto è più lunga del limite di dimensioni attuale)
m [i, s] = max (m [i-1, s], \, m [i-1, s-si] + si) se si minore o uguale a s.
La soluzione può quindi essere trovata calcolando m [n, d].
chiamiamo s, la somma della lunghezza delle auto nella soluzione dal problema dello zaino. Se la somma di tutte le lunghezze della vettura - s è inferiore o uguale a d, allora tutte le auto considerate per risolvere i problemi dello zaino possono entrare nel traghetto (una corsia essendo tutte quelle selezionate per far parte della soluzione zaino, l'altra corsia essendo il resto). Se la somma della lunghezza del resto delle auto è superiore a d, allora tutte le auto non possono entrare nel traghetto. Rimuovi l'ultima auto dall'elenco delle auto e risolvi nuovamente il problema dello zaino. Fallo fino a quando la somma della lunghezza delle auto non selezionate è inferiore a d
La complessità dell'algoritmo DP per risolvere il problema dello zaino è O (nd) e deve essere risolta al massimo n volte - > complessità O (n ^ 2d)
Ecco uno schizzo della soluzione 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()