Programmazione dinamica

[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 ?

[frog831]

Guarda su un qualunque libro di Algoritmi e struttute dati!

[cicciox80]

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 ?

[Angioletto]

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]

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)

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]

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!

[DaUlisse]

Ti sei scelto l'argomento + bastardo..almeno secondo me
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