Programmazione dinamica - La più ampia disposizione di librerie

5

Sto cercando di risolvere un problema, quindi non sto cercando codice, ma per algoritmi simili, quindi posso risolverlo da solo.

Mi viene dato n di librerie ciascuna con una quantità di size di libri all'interno. Devo spostare alcuni di queste librerie in una nuova stanza come segue:

  • La prima libreria verrà sempre spostata;
  • Terrò l'ordine delle librerie nella nuova stanza (non posso cambiare posizione nella nuova stanza);
  • Libreria non posso essere posizionata accanto a uno dei bookcases i-1 o i+1 (es: non riesco a posizionare? -4-5 -? /? - 5-6 -? /? - 4-5 -6 -);?

Quindi la libreria 1 è sempre nella nuova stanza. Inoltre, se la libreria i è nella stanza, né i-1 , né i+1 saranno nella stanza.

Quale configurazione di librerie mi offrirà la più grande quantità di libri?

Capisco che ciò sia risolto utilizzando un algoritmo di programmazione dinamica, ma non sono sicuro di quale sia. Inizialmente pensavo che sarebbe stato simile al problema dello zaino, ma non ho un limite di libri, quindi è chiaramente diverso (almeno penso che lo sia). La complessità del target è O (n), ma qualsiasi idea mi aiuterà a farlo.

    
posta Xzenon 15.03.2016 - 23:25
fonte

1 risposta

1

Questo problema è simile al problema la sottosequenza crescente più lunga . Diciamo che memorizziamo il numero di libri all'interno di ogni libreria in un array N.

N[i] = number of books in bookcase i.

Mantieni un array S, dove S [i] è il valore massimo che puoi ottenere nell'altra stanza usando un sottoinsieme degli elementi da 1 a i che contiene l'elemento i.

S[ 1 ] = N[ 1 ]

S[ i ] = max( S[ 1 ], S[ 2 ], ... S[ i - 2 ] ) + N[ i ], for i = 3..N.Size

La risposta sarà quindi il valore max(S[N.Size], S[N.Size - 1]) . Per ottenere gli elementi reali che prendi puoi conservare ulteriori informazioni in un altro array PREV [i] - L'elemento prima di i nella nuova stanza.

Questo tempo viene eseguito in O (n ^ 2), ma puoi migliorarlo a O (nlogn) usando alberi ad intervalli o alberi indicizzati binari per ottenere il massimo in tempo logaritmico (simile al problema di sottosuccessione crescente più lungo)

Aggiornamento: appena realizzato che se i valori sono positivi, possiamo risolvere questo in O (n)

S[i] =max(S[i-2], S[i-3]) + N[i]

Ma se i valori possono essere negativi, questo non funzionerà

    
risposta data 16.03.2016 - 12:30
fonte

Leggi altre domande sui tag