Programmazione dinamica¶
Parte 3 del corso, volume 3 delle dispense: capitoli 16–28.
I principi della programmazione dinamica e gli algoritmi di PD per i problemi di zaino, il lot sizing, il cambio monete e il taglio delle aste: ricorrenze, pseudocodice, complessità e tabelle svolte.
-
16. Principi della programmazione dinamica
Dividere, conquistare, combinare · Proprietà del problema richieste dagli algoritmi di PD · Passi per progettare un algoritmo di PD · Gli algoritmi di PD di questo modulo
Problemi di zaino¶
-
17. PD per il problema dello zaino 0/1
Istanze e soluzioni ammissibili · Un primo algoritmo di PD · Un secondo algoritmo di PD
-
18. PD per il problema dello zaino illimitato
Istanze e soluzioni ammissibili · Un primo algoritmo di PD · Un secondo algoritmo di PD
-
19. PD per il problema dello zaino limitato
Istanze e soluzioni ammissibili · Un algoritmo di PD
-
20. PD per il problema del subset sum
Un algoritmo di PD
-
21. PD per il problema dello zaino a scelta multipla
Un algoritmo di PD
-
22. PD per il problema dello zaino multidimensionale
Un algoritmo di PD
-
23. PD per il problema dello zaino con setup
Un algoritmo di PD
-
24. PD per il problema degli zaini multipli
Un algoritmo di PD
Problemi di lot sizing¶
-
25. PD per il problema del lot sizing senza capacità
Notazione, modello e soluzioni ammissibili · Un algoritmo di PD per l'ULS
-
26. PD per il problema del lot sizing capacitato
Notazione, modello e soluzioni ammissibili · Un algoritmo di PD per il CLS
Problemi misti¶
-
27. PD per il problema del cambio monete
Istanze e soluzioni ammissibili · Un algoritmo di PD
-
28. PD per il problema del taglio delle aste
Istanze e soluzioni ammissibili · Un primo algoritmo di PD · Un secondo algoritmo di PD