PDA

Visualizza la versione completa : Programmazione dinamica


cicciox80
09-07-2004, 22:39
Qualcuno l'ha studiata ? E sa dove posso trovare esercizi svolti di progr. dinamica ?

Ad esempio, dato un vettore di N interi, trovare il sottovettore la cui somma sia massima.

Con la P.D. si pu fare in un tempo di O(N), ma qual' il procedimento ?

frog831
12-07-2004, 09:58
Guarda su un qualunque libro di Algoritmi e struttute dati!

cicciox80
12-07-2004, 12:16
Originariamente inviato da frog831
Guarda su un qualunque libro di Algoritmi e struttute dati!

Ce ne ho uno ma ci sono solo tre esempi particolari... Dico io ma su internet non c' qualche esercizio svolto ? :cry:

Angioletto
12-07-2004, 15:34
Originariamente inviato da cicciox80
Qualcuno l'ha studiata ? E sa dove posso trovare esercizi svolti di progr. dinamica ?

Ad esempio, dato un vettore di N interi, trovare il sottovettore la cui somma sia massima.

Con la P.D. si pu fare in un tempo di O(N), ma qual' il procedimento ?

programmazione dinamica? riguarda forse l'uso di puntatori dinamici??

cmq, credo che dovresti conoscere la dimensione del sottovettore, che supponiamo sia M. Allora preleva dal vettore lungo N l'elemento + grande e lo metti in M, poi passi al sottovettore lungo N-1 e ripeti la stessa cosa, fino a riempire il vettore M.
Magari puoi ordinare il vettore di partenza prima di fare questo: se in ordine crescente prelevi gli ultimi M elementi..

cicciox80
12-07-2004, 17:52
Originariamente inviato da Angioletto
programmazione dinamica? riguarda forse l'uso di puntatori dinamici??

cmq, credo che dovresti conoscere la dimensione del sottovettore, che supponiamo sia M. Allora preleva dal vettore lungo N l'elemento + grande e lo metti in M, poi passi al sottovettore lungo N-1 e ripeti la stessa cosa, fino a riempire il vettore M.
Magari puoi ordinare il vettore di partenza prima di fare questo: se in ordine crescente prelevi gli ultimi M elementi..

mi sa che nn hai capito (o non mi sono spiegato bene) :fagiano:

Faccio un esempio: ho in input il vettore:

1 -2 3 5 -2 3 -1 0

Il sottovettore risultante sar:

3 5 -2 3

questo perch ha somma 9 che il massimo.

Quindi come risultato basta dare gli indici 3 e 6 (il sottoarray parte dal terzo elemento al sesto).

La programmazione dinamica non riguarda i puntatori: una tecnica di risoluzione dei problemi di ottimizzazione

Angioletto
12-07-2004, 18:19
ottimo..
non avevo capito assolutamente nulla!

anche gli elementi del vettore devono essere consecutivi: pensavo dovessi prendere quelli che, messi insieme, ti fornivano la somma massima..

spiacente, non posso esserti di aiuto! :cry:

DaUlisse
12-07-2004, 18:44
:D :D :D
Ti sei scelto l'argomento + bastardo..almeno secondo me:D
Be in internet ci sono un paio di dispense sul sito delle olimpiadi di informatica; quando me le hanno mostrate le ho trovate poco chiare ma approfondendo meglio ti accorgerai che sono fatte bene!!!

http://ioi.dsi.unimi.it/

Buon divertimento!
X me lo e' stato anche se nn spadroneggio ancora con l'argomento :(

Loading