Dynamic Programming
L’idea è EVITARE di ricalcolare cose già fatte Ce le siamo già salvate da qualche parte (es. tabella)
Iter di un algoritmo:
- risolvo in maniera ricorsiva
- se ci sono sottopr ripetuti
- dinamica
- se ce ne sono solo alcuni
- memoization / tabulation
- se non ce ne sono
- divide et impera
- se ci sono sottopr ripetuti
Concetti
Video
- questa playlist per bene: https://www.youtube.com/watch?v=1mtvm2ubHCY&list=PLl0KD3g-oDOGJUdmhFk19LaPgrfmAGQfo&index=2
- https://www.youtube.com/watch?v=jTjRGe0wRvI&list=PLVrpF4r7WIhTT1hJqZmjP10nxsmrbRvlf
Problemi
Domino
- domino
- input intero n, rest numero di possibili disposizioni di n tessere in un rettangolo 2xN
- ricorrenza
- partiamo dai casi base
- quante disp possibili se non ho tessere? 1
- quante disp possibili se ho 1 tessera? sempre 1
- e le altre? DP[n-1]+DP[n-2]
- partiamo dai casi base
La complessità qua è bruttissima: 2
Allora usiamo una tabella DP, dove memorizziamo i risultati intermedi.
Se uso una tabella, tempo e spazio diminuiscono, perché uso un array dove vado ad accedere alle singole celle. Il costo è costante ed è n.
Le prime due volte mi inizializzo i valori a 1, e poi da 2 a n mi calcolo nell’i-esima posizione, elem. i-1 nella tabella + elem. i-2
Hatesville
- Hatesville
- dato un insieme di case che possono effettuare donazioni, ponendo che nessun vicino dona se entrambi i vicini donano, trovare un algoritmo che restituisca il num. max possibile di donazioni
- es. [4, 3, 6, 5] risposta: indici 1,3 (10 è il massimo)
- Occorre ridefinire il problema
- sia HV(i) uno dei possibili insiemi di indici da selezionare per ottenere una donazione ottimale dalle prime i case di Hateville, numerate 1…n
- HV(n) è la sol. del problema originale
- HV(i) = highest(HV(i-1), {i} U HV(i-2)}
- se non accetto la prima, se accetto la seconda perché poi no? la storia del vicino…
Un algoritmo di prog. dinamica si dimostra quando puoi dim che è una sottostruttura ottima.
Memorizzare insiemi in un array fa schifo come soluzione, allora uso sempre un approccio basato su valore: mi costruisco un array DP e lavoro su quello. DP[i] sarà dato da max(DP[i-1], DP[i-2] + D[i]) se non accetto, se accetto
Zaino
Dato un insieme di oggetti caratterizzato da peso e profitto, e uno zaino con un limite di capacità, trovare il miglior insieme di sotto-oggetti in modo tale che il peso sia inferiore alla capacità dello zaino e il valore totale degli oggetti sia massimale
Mentre programmi greedy devi SEMPRE partire dall’ultimo elemento
problema di massimizzazione? max. sempre. max tra qualcosa.
in questo caso: se non prendo l’oggetto, DP[i-1][c]
se lo prendo: DP[i-1][c-w[i]]+p[i], dove p è profitto e w è peso.