Quale sarebbe un algoritmo O (n) per massimizzare le scelte da un elenco quando puoi scegliere solo 2 elementi da ogni 7 elementi. Ho pensato a questo problema per alcuni giorni e non riesco a capire una risposta. So che deve essere una soluzione di programmazione dinamica ma non riesco a vedere come collegare alcun sottoproblema. Cioè se hai 2, 1, 1, 1, 3, 4, 1, 20. Poi alla fine vuoi scegliere 2, 4, 20, ma 2 e 4 non sono mai stati una soluzione prima insieme.
Dal tuo commento
So like in 2,1,1,1,3,4,1 you can't pick more than two and also in 1,1,1,3,4,1,20 – Paula
Concludo che stiamo parlando di una finestra scorrevole di 7 elementi
.Questo elenco di 8 elementi
[2,1,1,1,3,4,1,20]
avrà due finestre di 7 elementi
[2,1,1,1,3,4,1]
[1,1,1,3,4,1,20]
da ognuno possiamo scegliere 2 oggetti. Vogliamo "massimizzare" queste scelte.
Suppongo che questo significhi voler massimizzare la media dei numeri selezionati.
Se "puoi scegliere solo 2 elementi" significa in realtà che devi sempre selezionare esattamente 2 elementi, quindi posso vedere come ottieni 2, 4 e 20. Nella prima finestra scegli 2 e 4, nella seconda finestra hai scegli 4 e 20. 4 vengono prelevati due volte.
Se volevi dire che possiamo prendere fino a 2 allora non avrei mai scelto 2 o 4. Solo 20. Questo mi lascia con una media molto più alta. Selezionerei un numero solo se stava per uscire dalla finestra ed era il più alto nella finestra (perché questa è l'ultima possibilità di prenderlo mentre ho più informazioni a riguardo) o se questa è l'ultima finestra I ' Prenderò il numero migliore.
Dato che la tua soluzione non è [20], è [2,4,20] presumo che dobbiamo scegliere esattamente 2 per ogni finestra. In tal caso è semplice. In ogni 7 scegli i primi due numeri e non raddoppiare quelli che hai scelto due volte.
La programmazione dinamica non è necessaria per questo.
Leggi altre domande sui tag algorithms dynamic-programming