Scrivere algoritmi dinamici

6.1 Passi principali nello sviluppo di algoritmi dinamici.

Passi principali nello sviluppo di algoritmi dinamici

1. Definizione dei sottoproblemi:

Dividi il problema in sottoproblemi più piccoli, che possono essere risolti indipendentemente l'uno dall'altro. Questi sottoproblemi devono sovrapporsi, in modo da poter utilizzare i risultati di calcoli precedenti.

2. Identificazione degli stati:

Determina tutti i possibili stati che possono sorgere nella risoluzione del problema. Gli stati devono descrivere tutte le informazioni necessarie per il passaggio da un passo all'altro.

3. Formulazione della relazione ricorrente:

Determina come la soluzione del problema per lo stato corrente dipenda dalle soluzioni per gli stati precedenti. Questa relazione deve esprimere come ottenere la soluzione ottimale utilizzando le soluzioni per i sottoproblemi.

4. Definizione dei casi base:

Determina i casi base per i quali la soluzione al problema è nota direttamente, senza la necessità di ulteriori calcoli.

5. Riempimento della tabella:

Crea una tabella (di solito un array o una matrice) per memorizzare le soluzioni di tutti i sottoproblemi. Usa la relazione ricorrente e i casi base per riempire la tabella dal basso verso l'alto o dall'alto verso il basso.

6. Ottimizzazione (memoizzazione):

Se si utilizza un approccio ricorsivo, aggiungi la memoizzazione per salvare i risultati dei sottoproblemi ed evitare di ricalcolarli.

Complessità temporale e spaziale degli algoritmi dinamici

Complessità temporale:

• La complessità temporale degli algoritmi dinamici è spesso espressa attraverso il numero di sottoproblemi e il tempo necessario per calcolare ciascun sottoproblema.
• Nella maggior parte dei casi, la complessità temporale è O(n) o O(n^2), dove n è la dimensione dei dati di input.

Complessità spaziale:

• La complessità spaziale dipende dal numero di stati che devono essere memorizzati.
• In alcuni casi è possibile ridurre la complessità spaziale tramite ottimizzazioni, come ridurre la memoria utilizzata a O(n) o O(1).

6.2 Problema dello zaino.

Il problema dello zaino è un classico problema di ottimizzazione combinatoria, che si verifica in vari ambiti, tra cui l'informatica, l'economia e la gestione della logistica. L'obiettivo principale del problema è utilizzare in modo più efficiente possibile le risorse limitate.

Descrizione del problema dello zaino

Si ha uno zaino che può sostenere un certo peso W. Sono disponibili anche n oggetti, ognuno dei quali ha un certo peso wt[i] e un valore val[i]. Devi determinare quali oggetti prendere per massimizzare il valore complessivo degli oggetti nello zaino senza superare la sua capacità di peso.

Tipi di problema dello zaino

1. Problema dello zaino 0/1 (0/1 Knapsack Problem):

Ogni oggetto può essere preso o non preso (non è possibile prenderlo parzialmente).

2. Problema del frazionamento dello zaino (Fractional Knapsack Problem):

Ogni oggetto può essere diviso e se ne può prendere qualsiasi parte.

3. Problema dello zaino multiplo (Multiple Knapsack Problem):

Ci sono diversi zaini con diversi limiti di peso.

Formulazione del problema dello zaino 0/1 in termini di teoria degli algoritmi:

Relazione ricorrente:

Per ogni oggetto i e per ogni peso possibile w (da 0 a W), la soluzione ottimale può essere espressa nel modo seguente:

• Se l'oggetto i non è incluso nello zaino, il valore ottimale è il valore ottimale per i − 1 oggetti e peso w.
• Se l'oggetto i è incluso nello zaino, il valore ottimale è il valore di quell'oggetto più il valore ottimale per i − 1 oggetti e peso w − wt[i].

Complessità temporale e spaziale

Complessità temporale:

La complessità temporale di questo algoritmo è O(nW) dove n è il numero di oggetti e W è la capacità dello zaino. Questo perché è necessario riempire una tabella di dimensioni n × W.

Complessità spaziale:

La complessità spaziale è anch'essa O(nW), perché è necessaria una tabella per memorizzare i risultati intermedi.

Esempi di implementazione del problema dello zaino 0/1

def knapsack(W, wt, val, n):
    # Creiamo una tabella per memorizzare i valori intermedi
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]
        
    # Riempiamo la tabella dp dal basso verso l'alto
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif wt[i - 1] <= w:
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]
        
    return dp[n][W]
        
# Esempio di utilizzo
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(f"Valore massimo per lo zaino: {knapsack(W, wt, val, n)}")
        

6.3 Problema del cambio di monete.

Il problema del cambio di monete è un classico problema di programmazione dinamica, che consiste nel trovare il numero minimo di monete o il numero di modi per comporre una certa somma di denaro a partire da un insieme di monete con denominazioni date. Questo problema ha due varianti principali:

Numero minimo di monete (Minimum Coin Change Problem):

Trovare il numero minimo di monete che compone una data somma.

Numero di modi (Number of Ways to Make Change):

Trovare il numero di modi diversi per comporre una data somma con l'insieme di monete dato.

Variante 1. Numero minimo di monete

Formulazione del problema

Dati:

• Set illimitato di monete con denominazioni date.
• Somma target S.

Necessario:

• Trovare il numero minimo di monete che compone la somma S.

Soluzione con programmazione dinamica

Relazione ricorrente:

• Sia dp[i] il numero minimo di monete necessario per comporre la somma i.
• Per ogni moneta c dell'insieme di monete, se i ≥ c, allora: dp[i] = min(dp[i], dp[i − c] + 1)

Casi base:

• dp[0] = 0 (per somma 0 servono 0 monete).

Complessità temporale e spaziale:

• Complessità temporale: O(n ⋅ S), dove n è il numero di denominazioni di monete, S è la somma target.
• Complessità spaziale: O(S), dato che è necessario un array per memorizzare il numero minimo di monete per ogni somma da 0 a S.

Esempio di implementazione in Python

def min_coins(coins, S):
    dp = [float('inf')] * (S + 1)
    dp[0] = 0
        
    for i in range(1, S + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)
        
    return dp[S] if dp[S] != float('inf') else -1
        
# Esempio di utilizzo
coins = [1, 2, 5]
S = 11
print(f"Numero minimo di monete per somma {S}: {min_coins(coins, S)}")
        
        

Il problema del cambio di monete dimostra la flessibilità della programmazione dinamica. Viene utilizzato per l'insegnamento e la ricerca di tecniche algoritmiche, poiché mostra come usare le relazioni ricorrenti e i casi base per risolvere i problemi in modo efficiente.