Programmazione dinamica knapsack domande

Cos'è la programmazione dinamica?

È una tecnica di ottimizzazione per risolvere problemi complessi, dividendo in sottoproblemi più semplici e memorizzando i risultati.

Problema dello zaino definizione

È il problema di massimizzare il valore degli oggetti in uno zaino di capacità limitata.

Verità o Falsità: La programmazione dinamica è sempre la soluzione migliore.

Falsità: Non tutti i problemi ne beneficiano; a volte, algoritmi più semplici sono più efficaci.

Cosa rappresenta la capacità nello zaino?

La capacità rappresenta il limite massimo di peso o volume che lo zaino può contenere.

Esempio pratico del problema dello zaino.

Oggetti: (peso, valore) = [(2, 3), (3, 4), (4, 5)], Capacità = 5. Massimo valore = 7.

Causa → Effetto: Sottoproblemi nella programmazione dinamica.

Dividere un problema in sottoproblemi porta a soluzioni più efficienti e rapide.

Quali sono le fasi principali della programmazione dinamica?

1. Definizione del problema. 2. Identificazione dei sottoproblemi. 3. Memorizzazione dei risultati. 4. Combinazione delle soluzioni.

Funzione obiettivo nello zaino

Massimizzare il valore totale degli oggetti, rispettando la capacità dello zaino.

Cos'è la memoizzazione?

Tecnica per ottimizzare la programmazione dinamica, memorizzando i risultati dei sottoproblemi per evitarne il ricalcolo.

Confronto: Programmazione dinamica vs. Ricorsione.

Programmazione dinamica: più veloce, usa memoria. Ricorsione: più semplice, meno efficiente.

Completa: La soluzione del problema dello zaino è _____.

la combinazione di oggetti che massimizza il valore senza superare la capacità.

Qual è la complessità temporale della programmazione dinamica nel problema dello zaino?

È $\displaystyle O(n imes W)$, dove $\displaystyle n$ è il numero di oggetti e $\displaystyle W$ è la capacità dello zaino.

Problema dello zaino 0-1

Ogni oggetto può essere scelto o scartato. Utilizza la programmazione dinamica per massimizzare il valore totale.

Zaino frazionario

Oggetti possono essere frazionati. Si massimizza il valore totale dividendo gli oggetti in parti.

Vero o falso: il problema dello zaino è NP-completo.

Vero. Non esiste un algoritmo noto che risolva tutti i casi in tempo polinomiale.

Differenza tra 0-1 e zaino frazionario

0-1: oggetti interi. Frazionario: oggetti possono essere divisi.

Qual è l'algoritmo per lo zaino 0-1?

Utilizza una tabella per memorizzare i valori massimi. Formula: $\displaystyle K(i, w) = max(K(i-1, w), K(i-1, w-w_i) + v_i)$.

Esempio di zaino frazionario

Oggetti: (valore 60, peso 10), (valore 100, peso 20). Capacità zaino: 30. Prendi tutto del primo e il 50% del secondo.

Cosa rappresenta il valore di utilità?

È il valore totale ottenuto dagli oggetti nello zaino. Si cerca di massimizzarlo.

Zaino multidimensionale

Considera più vincoli (es. peso e volume). Richiede una programmazione dinamica più complessa.

Qual è un'applicazione pratica del problema dello zaino?

Pianificazione delle risorse in scenari di budget limitato, come investimenti o distribuzione di risorse.

Cause ed effetti nel 0-1 knapsack

Scelta di un oggetto → incremento del valore totale. Scelta non ottimale → valore inferiore.

Zaino con ripetizione

Ogni oggetto può essere scelto più volte. Utilizza una formula simile alla 0-1, ma consente ripetizioni.

Come si calcola il valore massimo nello zaino?

Confrontando ogni oggetto, aggiornando il valore totale in base alla capacità disponibile.