Alla ricerca di una soluzione di programmazione dinamica

Question

Alla ricerca di una soluzione di programmazione dinamica

#1 da (1 voti)
#2 da (1 voti)

4

Data una sequenza di numeri interi nell'intervallo da 1 a n. Ogni numero può apparire al massimo una volta. Lascia che ci sia un simbolo X nella sequenza che significa rimuovere l'elemento minimo dalla lista. Ci può essere un numero arbitrario di X nella sequenza. Esempio: 1,3,4, X, 5,2, X L'output è 1,2.

Dobbiamo trovare il modo migliore per eseguire questa operazione.

La soluzione che ho pensato è:

Analizza la sequenza da sinistra a destra e conta il numero di X che richiede il tempo O (n). Esegui l'ordinamento parziale e trova i k elementi più piccoli (k = numero di X) che impiega il tempo O (n + klogk) usando la mediana delle mediane.

C'è un modo migliore per risolvere questo problema usando la programmazione dinamica o in altro modo?

algorithms dynamic-programming

posta krammer 30.09.2012 - 15:11

fonte

2 risposte

Leggi altre domande sui tag algorithms dynamic-programming

Alternativa a XML / XSLT per la generazione di artefatti? Come adottare la metodologia di mischia agile per un piccolo team .Net [chiuso]

score 1 · Answer 1

È improbabile che la programmazione dinamica sia utile qui. Hai già ottenuto una soluzione O(n log n) , la programmazione dinamica tende ad essere più simile a O(n^2) o O(n^3) . (Ci sono delle eccezioni, ma non mi aspetterei di trovare una soluzione migliore qui.)

Quello che puoi vedere usando è un heap limitato alle dimensioni. In pratica, usa lo heap per contenere i valori di k più piccoli trovati finora. Per ogni nuovo valore, confronta con il valore più alto nell'heap e sostituiscilo se ne abbiamo uno inferiore.

A dire il vero, probabilmente avrai bisogno di alcuni grandi set di dati perché valga la pena di fare qualsiasi cosa se non invocare l'ordinamento incorporato della tua lingua e prendere una fetta.

score 1 · Answer 2

Non sembra che DP sarebbe di grande utilità per risolvere il tuo problema, perché non mostra la sottostruttura ottimale proprietà.

Il problema può essere risolto in modo molto efficiente con una coda di priorità : quando vedi un numero, annullarlo e aggiungere il risultato alla coda di priorità. Quando visualizzi un X , deseleziona il numero con la priorità più alta e lo annulla nuovamente prima di aggiungerlo alla risposta.