La programmazione dinamica è una tecnica algoritmica potente utilizzata per risolvere problemi complessi suddividendoli in sottoproblemi più piccoli e sovrapposti, risolvendo ciascun sottoproblema una sola volta e memorizzando le soluzioni per evitare di doverle ricalcolare in futuro.

In altre parole, la programmazione dinamica sfrutta il principio di “memorizzazione” (o “memoization”) per ottimizzare le prestazioni, specialmente in problemi con sottostrutture ottimali (ovvero, la soluzione di un problema può essere costruita a partire dalle soluzioni dei suoi sottoproblemi).

Caratteristiche principali della programmazione dinamica

1. Sottoproblemi sovrapposti: Il problema originale viene suddiviso in sottoproblemi più piccoli, alcuni dei quali possono essere comuni e quindi risolti più volte se non si utilizzasse la programmazione dinamica.
2. Sottostruttura ottimale: La soluzione ottima al problema principale può essere ottenuta combinando le soluzioni ottime dei suoi sottoproblemi.
3. Memorizzazione (o “memoization”): Le soluzioni dei sottoproblemi vengono memorizzate in una tabella (o struttura dati simile) per evitare di doverle ricalcolare ogni volta che si incontrano di nuovo.

Approcci alla programmazione dinamica

Esistono due approcci principali alla programmazione dinamica:

1. Top-down (ricorsivo con memoization):

   • Si parte dal problema principale e lo si suddivide ricorsivamente in sottoproblemi.
   • Prima di risolvere un sottoproblema, si controlla se la sua soluzione è già stata memorizzata.
   • Se la soluzione è già presente, viene restituita direttamente; altrimenti, il sottoproblema viene risolto, la soluzione viene memorizzata e quindi restituita.
   • Questo approccio è più intuitivo se il problema è già formulato in modo ricorsivo.

2. Bottom-up (tabulazione):

   • Si parte dai sottoproblemi più piccoli e si costruisce iterativamente la soluzione del problema principale.
   • Si utilizza una tabella per memorizzare le soluzioni dei sottoproblemi.
   • Si riempie la tabella in modo sistematico, calcolando le soluzioni dei sottoproblemi più grandi a partire dalle soluzioni dei sottoproblemi più piccoli.
   • Questo approccio è spesso più efficiente perché evita le chiamate ricorsive e il rischio di stack overflow.

Memoization vs Tabulation

• Memoization (Top-Down):

  • Si basa su una funzione ricorsiva che memorizza i risultati intermedi in una struttura dati, come un dizionario.
  • È più intuitiva se il problema è già formulato in modo ricorsivo.
  • Può comportare un consumo di memoria maggiore a causa della profondità della ricorsione.

• Tabulation (Bottom-Up):

  • Costruisce una tabella (array) partendo dai casi base e calcolando progressivamente i risultati successivi.
  • È spesso più veloce e riduce il rischio di superare il limite dello stack.
  • Può essere più complessa da implementare se il problema non è naturalmente iterativo.

Quando scegliere l’uno o l’altro?

• Se il problema è naturalmente ricorsivo e non si hanno limiti di stack, la memoization può essere più semplice.
• Se si vuole migliorare l’efficienza eliminando la ricorsione, la tabulation è preferibile.

Vantaggi della programmazione dinamica

• Efficienza: Riduce il tempo di esecuzione evitando calcoli ridondanti.
• Ottimizzazione: Trova la soluzione migliore sfruttando le sottostrutture ottimali.
• Semplicità: Può semplificare la progettazione di algoritmi complessi.

Esempi di problemi risolvibili con la programmazione dinamica

• Calcolo del numero di Fibonacci
• Problema dello zaino
• Calcolo del cammino minimo in un grafo
• Allineamento di sequenze biologiche
• Moltiplicazione di matrici

Certo, ecco una descrizione approfondita del problema dello zaino:

Il problema dello zaino (Knapsack Problem)

Il problema dello zaino è un classico problema di ottimizzazione combinatoria. Immagina di avere uno zaino con una capacità massima di peso che puoi trasportare. Hai anche una serie di oggetti, ognuno con un peso e un valore specifici. L’obiettivo è scegliere quali oggetti mettere nello zaino in modo da massimizzare il valore totale degli oggetti trasportati, senza superare la capacità massima dello zaino.

Formulazione del problema

• Input:
  • capacità: La capacità massima dello zaino (un numero intero).
  • oggetti: Una lista di oggetti, dove ogni oggetto è rappresentato da una tupla (peso, valore) (numeri interi).
• Output:
  • Il valore massimo totale degli oggetti che possono essere inseriti nello zaino senza superare la capacità massima.

Esempio

Supponiamo di avere uno zaino con una capacità massima di 50 kg e i seguenti oggetti:

Oggetto	Peso (kg)	Valore (€)
A	10	60
B	20	100
C	30	120

Quali oggetti dovremmo mettere nello zaino per massimizzare il valore totale?

Approcci di risoluzione

Il problema dello zaino può essere risolto utilizzando diversi approcci, tra cui:

• Forza bruta: Si provano tutte le combinazioni possibili di oggetti e si sceglie quella che massimizza il valore totale senza superare la capacità massima. Questo approccio è inefficiente per un numero elevato di oggetti.
• Algoritmo greedy: Si ordinano gli oggetti in base al rapporto valore/peso e si aggiungono gli oggetti allo zaino fino a quando non si raggiunge la capacità massima. Questo approccio non garantisce la soluzione ottima in tutti i casi.
• Programmazione dinamica: Questo approccio è efficiente e garantisce di trovare la soluzione ottima. Si basa sulla suddivisione del problema in sottoproblemi più piccoli e sulla memorizzazione dei risultati per evitare di doverli ricalcolare.

Programmazione dinamica per il problema dello zaino

L’approccio di programmazione dinamica per il problema dello zaino utilizza una tabella (o matrice) per memorizzare i risultati dei sottoproblemi. La tabella ha dimensioni (n + 1) x (capacità + 1), dove n è il numero di oggetti. tabella[i][c] rappresenta il valore massimo ottenibile considerando i primi i oggetti e una capacità massima c.

La tabella viene riempita in modo bottom-up, partendo dai sottoproblemi più piccoli (con 0 oggetti o capacità 0) e arrivando al problema principale (con tutti gli oggetti e la capacità massima). Per ogni cella tabella[i][c], si considera se l’oggetto i può essere incluso nello zaino (cioè se il suo peso è minore o uguale alla capacità c). Si sceglie il massimo tra includere o escludere l’oggetto i e si memorizza il risultato nella tabella.

Vantaggi della programmazione dinamica

• Efficienza: La programmazione dinamica è un approccio efficiente per risolvere il problema dello zaino, soprattutto per un numero elevato di oggetti.
• Ottimalità: La programmazione dinamica garantisce di trovare la soluzione ottima al problema dello zaino.

def problema_zaino(capacita, oggetti):
    """
    Risolve il problema dello zaino utilizzando la programmazione dinamica.

    Args:
        capacita: La capacità massima dello zaino (intero).
        oggetti: Una lista di tuple, dove ogni tupla rappresenta un oggetto e contiene il suo peso e valore (interi).

    Returns:
        Il valore massimo degli oggetti che possono essere inseriti nello zaino.
    """

    n = len(oggetti)  # Numero di oggetti
    # Creazione di una tabella (matrice) per memorizzare i risultati dei sottoproblemi
    # La tabella ha dimensioni (n + 1) x (capacita + 1)
    # tabella[i][c] rappresenta il valore massimo ottenibile considerando i primi i oggetti e una capacità massima c
    tabella = [[0] * (capacita + 1) for _ in range(n + 1)]

    # Iterazione sugli oggetti
    for i in range(1, n + 1):
        # Iterazione sulle capacità
        for c in range(1, capacita + 1):
            peso = oggetti[i - 1][0]  # Peso dell'oggetto corrente (ricorda che gli indici partono da 0)
            valore = oggetti[i - 1][1]  # Valore dell'oggetto corrente

            # Se il peso dell'oggetto corrente è minore o uguale alla capacità corrente
            if peso <= c:
                # Si considera il massimo tra:
                # 1. Includere l'oggetto corrente: valore + valore massimo ottenibile con i rimanenti oggetti e la capacità residua (c - peso)
                # 2. Escludere l'oggetto corrente: valore massimo ottenibile con i precedenti oggetti e la stessa capacità c
                tabella[i][c] = max(valore + tabella[i - 1][c - peso], tabella[i - 1][c])
            else:
                # Se il peso dell'oggetto corrente è maggiore della capacità corrente, non possiamo includerlo
                # Quindi, il valore massimo ottenibile è lo stesso di quello ottenibile con i precedenti oggetti e la stessa capacità c
                tabella[i][c] = tabella[i - 1][c]

    # Il risultato finale si trova in tabella[n][capacita], ovvero il valore massimo ottenibile considerando tutti gli oggetti e la capacità massima dello zaino
    return tabella[n][capacita]


# Esempio di utilizzo
capacita = 50  # Capacità massima dello zaino
oggetti = [(10, 60), (20, 100), (30, 120)]  # Lista di oggetti: (peso, valore)
valore_massimo = problema_zaino(capacita, oggetti)  # Calcolo del valore massimo
print(f"Valore massimo ottenibile: {valore_massimo}")  # Stampa del risultato

Spiegazione passo per passo con evidenziazione dell’approccio alla programmazione dinamica

1. Definizione della funzione problema_zaino(capacita, oggetti):

   • La funzione prende in input la capacità massima dello zaino (capacita) e una lista di oggetti (oggetti), dove ogni oggetto è una tupla contenente il suo peso e valore.
   • L’obiettivo è determinare il valore massimo degli oggetti che possono essere inseriti nello zaino senza superare la capacità massima.

2. Inizializzazione della tabella:

   • Viene creata una tabella (matrice) chiamata tabella di dimensioni (n + 1) x (capacita + 1), dove n è il numero di oggetti.
   • tabella[i][c] rappresenta il valore massimo ottenibile considerando i primi i oggetti e una capacità massima c.
   • La prima riga e la prima colonna della tabella vengono inizializzate con 0, poiché non si possono ottenere valori con 0 oggetti o capacità 0.

3. Iterazione sugli oggetti e sulle capacità:

   • Vengono utilizzati due cicli for nidificati per iterare su tutti gli oggetti e tutte le capacità possibili.
   • Per ogni oggetto i e capacità c, si considera se l’oggetto corrente può essere incluso nello zaino (cioè se il suo peso è minore o uguale alla capacità corrente).

4. Decisione se includere o escludere l’oggetto corrente:

   • Se il peso dell’oggetto corrente è minore o uguale alla capacità corrente, si deve scegliere tra due opzioni:
     1. Includere l’oggetto corrente: In questo caso, il valore massimo ottenibile è il valore dell’oggetto corrente più il valore massimo ottenibile con i rimanenti oggetti e la capacità residua (c - peso).
     2. Escludere l’oggetto corrente: In questo caso, il valore massimo ottenibile è lo stesso di quello ottenibile con i precedenti oggetti e la stessa capacità c.
     • Si sceglie l’opzione che produce il valore massimo e si memorizza nella tabella.
   • Se il peso dell’oggetto corrente è maggiore della capacità corrente, non possiamo includerlo, quindi il valore massimo ottenibile è lo stesso di quello ottenibile con i precedenti oggetti e la stessa capacità c.

5. Restituzione del risultato:

   • Il risultato finale si trova in tabella[n][capacita], ovvero il valore massimo ottenibile considerando tutti gli oggetti e la capacità massima dello zaino.

Approccio alla programmazione dinamica

L’algoritmo del problema dello zaino presentato sopra utilizza un approccio di programmazione dinamica bottom-up (tabulazione). Ecco come si applicano i concetti chiave della programmazione dinamica:

• Sottoproblemi sovrapposti: Il problema dello zaino può essere suddiviso in sottoproblemi più piccoli, ovvero trovare il valore massimo ottenibile con un sottoinsieme degli oggetti e una capacità massima inferiore. Questi sottoproblemi sono sovrapposti, cioè alcuni di essi vengono risolti più volte durante il processo di risoluzione.
• Sottostruttura ottimale: La soluzione ottima al problema dello zaino può essere costruita a partire dalle soluzioni ottime dei suoi sottoproblemi. In altre parole, il valore massimo ottenibile con un insieme di oggetti e una capacità massima può essere calcolato combinando i valori massimi ottenibili con sottoinsiemi di oggetti e capacità inferiori.
• Memorizzazione (tabulazione): La tabella tabella viene utilizzata per memorizzare i risultati dei sottoproblemi. In questo modo, evitiamo di dover ricalcolare più volte gli stessi risultati, ottenendo un’efficienza significativamente maggiore rispetto a un approccio ricorsivo semplice (che porterebbe a molti calcoli ridondanti).

Tipologie di problema dello zaino

Finora abbiamo considerato la versione 0/1 del problema dello zaino, dove ogni oggetto può essere preso o non preso. Tuttavia, esistono anche altre varianti che vale la pena conoscere. Ad esempio, nel problema dello zaino frazionario, è possibile prendere una frazione di un oggetto, ottenendo una proporzione del suo valore. Questa variante è più semplice da risolvere e può essere ottimizzata con un approccio greedy. Un’altra variante interessante è il problema dello zaino multiplo, dove sono disponibili più istanze dello stesso oggetto. In questo caso, l’obiettivo è decidere quante copie di ciascun oggetto prendere, tenendo sempre presente il limite di capacità dello zaino. Questa variante è più complessa da risolvere e richiede algoritmi specifici.

• Problema dello zaino frazionario (Fractional Knapsack Problem): In questa variante, è possibile prendere una frazione di un oggetto. Ad esempio, se hai un oggetto che pesa 10 kg e vale 60€, puoi decidere di prenderne solo metà (5 kg) e ottenere metà del valore (30€). Questo tipo di problema è più semplice da risolvere rispetto alla versione 0/1 e può essere ottimizzato con un approccio greedy (si ordinano gli oggetti in base al rapporto valore/peso e si prendono le frazioni degli oggetti più “convenienti” fino a riempire lo zaino).

• Problema dello zaino multiplo (Multiple Knapsack Problem): In questa variante, sono disponibili più istanze dello stesso oggetto. Ad esempio, potresti avere 3 copie dell’oggetto A, 2 copie dell’oggetto B e così via. L’obiettivo è decidere quante istanze di ciascun oggetto prendere per massimizzare il valore totale, rispettando sempre il limite di capacità dello zaino. Questa variante è più complessa da risolvere rispetto alla versione 0/1 e richiede algoritmi più sofisticati, come la programmazione dinamica multidimensionale.

Pubblicità