Alla ricerca di un algoritmo DP per un problema di imballaggio specifico

5

Ho il seguente problema da risolvere:

Dato un traghetto con una lunghezza d e un elenco di n auto con la loro lunghezza, dobbiamo caricare le auto sul traghetto in un ordine in cui appaiono nella lista su 2 corsie diverse (ognuna con lunghezza d). Scrivi un programma che ha una lunghezza d e l'elenco delle macchine emette il numero massimo di auto che possono essere caricate sul traghetto.

È abbastanza facile da fare in O (2 ^ auto) con il backtracking - carichiamo l'auto a sinistra e proviamo tutte le possibilità, risparmiamo il massimo e carichiamo la macchina a destra e facciamo lo stesso risparmio massimo di nuovo.

Ma ho la sensazione che questo possa essere ridotto al tempo polinomiale con la programmazione dinamica. Come dire se il mio istinto è vero?

    
posta qiubit 20.01.2015 - 20:31
fonte

2 risposte

3

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()
    
risposta data 26.01.2015 - 17:47
fonte
0

Questo è un problema con più zaino. Risolvendo con gli algoritmi Meet-in-the-middle, ci vuole O (2 ^ (n / 2)) per ogni "corsia".

partition the set {1...n} into two sets A and B of approximately equal size
compute the weights and values of all subsets of each set for each subset of A

find the subset of B of greatest value such that the combined weight is less than W
keep track of the greatest combined value seen so far

Maggiori dettagli qui: link

    
risposta data 28.01.2015 - 15:01
fonte

Leggi altre domande sui tag