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
oi+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.