dinamica programmazione algoritmo N, K problema

Question

Un algoritmo che avrà due numeri positivi N e K e calcolare il maggior numero possibile che possiamo ottenere trasformando N in un altro numero tramite la rimozione di K cifre da N.

Per ex, diciamo che abbiamo N = 12345 e K = 3 quindi il numero più grande che possiamo ottenere rimuovendo 3 cifre da N è 45 (altre trasformazioni sarebbero 12, 15, 35 ma 45 è il più grande). Inoltre, non è possibile modificare l'ordine delle cifre in N (quindi 54 NON è una soluzione). Un altro esempio sarebbe N = 66621542 e K = 3 quindi la soluzione sarà 66654.

So che questo è un problema di programmazione dinamica e non riesco a capire come risolverlo. Ho bisogno di risolvere questo per 2 giorni, quindi ogni aiuto è apprezzato. Se non vuoi risolvere questo per me non devi, ma per favore indicami il trucco o almeno alcuni materiali in cui posso leggere di più su alcuni problemi simili.

Grazie in anticipo.

Answer 1

Il trucco per risolvere un problema di programmazione dinamica è di solito capire come si presenta la struttura di una soluzione, e in particolare se presenta la sottostruttura ottimale.

In questo caso, mi sembra che la soluzione ottimale con N = 12345 e K = 3 avrebbe una soluzione ottimale per N = 12345 e K = 2 come parte della soluzione. Se riesci a convincerti che ciò vale, dovresti essere in grado di esprimere una soluzione al problema in modo ricorsivo. Quindi, implementalo con memoisation o bottom-up.

Answer 2

Ecco quello che penso:

consideri il primo k + 1 numeri a sinistra. Cerca il più grande, trovalo e rimuovi i numeri a sinistra. Se esistono due dello stesso numero più grande, trovare quello più a sinistra e rimuovere i numeri a sinistra di quello. memorizzare il numero di cifre rimosse (chiamarlo j).

Fai la stessa cosa con il nuovo numero come N e k + 1-j come K. Fai questo finché k + 1 -j è uguale a 1 (si spera, lo farà, se non mi sbaglio).

Il numero che si finisce con sarà il numero che stai cercando.

Answer 3

I due elementi più importanti di qualsiasi soluzione di programmazione dinamica sono:

1. Definire il giusto sottoproblemi
2. definire una relazione ricorrenza tra la risposta ad un sotto-problema e la risposta alle più piccole sotto-problemi
3. Trovare casi di base, il più piccolo sotto-problemi la cui risposta non dipende da eventuali altre risposte
4. Capire la ordine di scansione in cui si deve risolvere i sottoproblemi (in modo che si mai utilizzare la relazione di ricorrenza in base a dati non inizializzati)

Saprete che avete i giusti sottoproblemi definito quando

• il problema è necessario la risposta a è uno di loro
• I casi di base sono davvero banali
• la ricorrenza è facile valutare
• L'ordine di scansione è semplice

Nel tuo caso, è semplice per specificare i sottoproblemi. Poiché probabilmente si tratta di compiti a casa, ti darò il suggerimento che potresti desiderare che N avesse meno cifre da avviare con.

Answer 4

Bene, per risolvere qualsiasi problema di programmazione dinamica, è necessario suddividerlo in sottovoci ricorrenti.

Dire che definiamo il tuo problema come A (n, k), che restituisce il maggior numero possibile rimuovendo k cifre da n.

Possiamo definire un semplice algoritmo ricorsivo da questo.

Usando il tuo esempio, A (12345, 3) = max {A (2345, 2), A (1345, 2), A (1245, 2), A (1234, 2)}

Altro generalmente, A (n, k) = max {A (n con 1 cifra rimossa, k - 1)}

E il caso base è A (n, 0) = n.

Utilizzando questo approccio, è possibile creare una tabella che memorizza nella cache i valori di n e k.

int A(int n, int k) 
{ 
    typedef std::pair<int, int> input; 
    static std::map<input, int> cache; 

    if (k == 0) return n; 

    input i(n, k); 
    if (cache.find(i) != cache.end()) 
    return cache[i]; 

    cache[i] = /* ... as above ... */ 

    return cache[i]; 
} 

Ora, questa è la soluzione semplice, ma esiste una soluzione migliore che funziona con una cache monodimensionale molto piccola. Prendi in considerazione la riformulazione della domanda in questo modo: "Dato una stringa n e un intero k, trova la sottosequenza lessicograficamente più grande in n di lunghezza k". Questo è essenzialmente il tuo problema e la soluzione è molto più semplice.

Possiamo ora definire una diversa funzione B (i, j), che dà la più grande sequenza lessicografico di lunghezza (i - j), utilizzando solo i primi i cifre n (in altre parole, dopo aver rimosso j cifre dal primo i cifre di n).

Utilizzando ancora una volta il tuo esempio, avremmo:

B (1, 0) = 1

B (2, 0) = 12

B (3, 0) = 123

B (3, 1) = 23

B (3, 2) = 3

ecc

Con un po 'di pensiero, possiamo trovare la relazione di ricorrenza:

B (i, j) = max (10B (i-1, j) + n _i, B (i-1, j-1))

o, se j = i poi B (i, j) = B (i-1, j-1)

e B (0, 0) = 0

e si può codificare che in un modo molto simile al precedente.

Answer 5

Questo può essere risolto in O (L) dove L = numero di cifre. Perché usare formule DP complicate quando si può usare una pila per fare questo:

Per: 66.621.542 Aggiungi una cifra nello stack, mentre ci sono meno o uguale a L - K cifre sullo stack: 66621. Ora, rimuovere le cifre dalla pila mentre sono inferiori alla cifra attualmente letta e inserire la cifra corrente nello stack:

leggi 5: 5> 2, rilascia 1 in pila. 5> 2, anche pop 2. put 5: 6665 leggi 4: stack isnt full, put 4: 66654 read 2: 2 < 4, non fare nulla.

Hai bisogno di un'altra condizione: assicurati di non estrarre più elementi dalla pila di quante cifre ci siano nel tuo numero, altrimenti la tua soluzione sarà incompleta!

altro esempio: 12345 L = 5, K = 3 put L - K = 2 cifre in pila: 12

letto 3, 3> 2, pop 2, 3> 1, pop 1, mettere 3.stack: 3 leggi 4, 4> 3, pop 3, put 4: 4 leggi 5: 5> 4, ma non possiamo inserire 4, altrimenti non resteranno cifre sufficienti. quindi premere 5: 45.