Risolto il problema dello zaino 0/1 utilizzando l'esempio di programmazione dinamica

Qual è il problema dello zaino?

Migliori Problema dello zaino è un classico problema di ottimizzazione combinatoria. Un supermercato immagazzina n pacchetti (n ≤ 100). Pacchetto i ha peso W[i] ≤ 100 e valore V[i] ≤ 100. Un ladro non può trasportare un peso superiore alla capacità M (M ≤ 100). Quali pacchi dovrebbe prendere il ladro per massimizzare il valore totale?

Ingresso:

• Il peso massimo M ed il numero di colli n.
• Array di peso W[i] e valore corrispondente V[i].

Produzione:

• Valore totale massimo ottenibile entro i limiti della capacità.
• L'insieme esatto dei pacchi che il ladro dovrebbe portare via.

L'algoritmo dello zaino si divide in due varianti ben note:

• 0/1 Problema con lo zaino Risolto tramite programmazione dinamica. Ogni pacchetto viene preso per intero o scartato, senza parti parziali né duplicati.
• Problema dello zaino frazionario Risolto con una strategia avida. Qui puoi prendere una frazione di qualsiasi pacchetto per riempire la capacità rimanente.

Come risolvere il problema dello zaino utilizzando la programmazione dinamica con esempio

Il metodo "divide et impera" scompone un problema complesso in sottoproblemi, continuando a suddividere fino a quando ciascun sottoproblema non risulta semplice. La ricorsione pura, al contrario, spesso risolve lo stesso sottoproblema più volte, sprecando risorse.

L'idea centrale della programmazione dinamica dello zaino è quella di memorizzare ogni sottoproblema risolto in una tabella. Le chiamate ripetute leggono la risposta invece di ricalcolarla, trasformando una ricorsione esponenziale in codice a tempo polinomiale.

Risolvi il problema dello zaino utilizzando la programmazione dinamica

Per progettare una soluzione di programmazione dinamica, è necessario seguire quattro passaggi:

• Risolvi prima i sottoproblemi più piccoli.
• Ricavare una relazione di ricorrenza che permetta di costruire la soluzione di un sottoproblema a partire da problemi più piccoli.
• Memorizza le risposte ai sottoproblemi in una tabella calcolata dal basso verso l'alto utilizzando la relazione di ricorrenza.
• Ricava la risposta finale utilizzando i dati presenti nella tabella.

Analizza il problema dello zaino 0/1

Il valore ottimale dipende da due fattori indipendenti:

1. Quanti pacchetti sono ancora in fase di valutazione?
2. Il peso rimanente che lo zaino può ancora contenere.

Poiché la funzione obiettivo dipende da due quantità, la tabella delle opzioni deve essere bidimensionale. Sia B[i][j] indica il valore massimo quando si sceglie tra i pacchetti {1, …, i} con limite di peso j.

• La risposta finale è B[n][M], il miglior valore totale su tutti gli n pacchetti con capacità M.
• Il peso totale selezionato è sempre limitato dalla capacità attuale: B[i][j] ≤ j.

Esempio: se B[4][10] = 8, il peso totale migliore dei primi quattro pacchi con capacità inferiore a 10 è 8. Alcuni di questi quattro pacchi possono essere saltati.

Formula per calcolare B[i][j]

• W[i], V[i] sono il peso e il valore del pacchetto i, dove i è in {1, …, n}.
• M è il peso massimo che lo zaino può trasportare.

Caso base con un pacchetto: per ogni capacità j ≥ W[1]:

B[1][j] = W[1]

Nel caso generale, decidere se includere il pacchetto i nella capacità j:

• Se il pacchetto i è saltato, B[i][j] è uguale al miglior valore utilizzando i pacchetti {1, …, i-1} con capacità j:

B[i][j] = B[i - 1][j]

• Se il pacchetto i è preso (consentito solo quando W[i] ≤ j), B[i][j] è uguale a V[i] più il valore migliore tra i pacchetti {1, …, i-1} con capacità j – W[i]:

B[i][j] = V[i] + B[i - 1][j - W[i]]

Scegli il candidato più grande tra i due.

Basi della Programmazione Dinamica

Combinando i due casi si ottiene la ricorrenza completa:

B[i][j] = max(B[i - 1][j], V[i] + B[i - 1][j - W[i]])

Il caso base è B[0][j] = 0 per ogni j, perché zero pacchetti danno zero valore indipendentemente dalla capacità.

Calcola la tabella delle opzioni

Costruisci B usando la ricorrenza. Una volta riempito B, la stessa tabella guida il trace-back che ricostruisce i pacchetti scelti. La tabella B ha n + 1 righe e M + 1 colonne:

• La riga 0 rappresenta il caso base, riempita con zeri.
• Utilizzare la riga 0 per calcolare la riga 1, la riga 1 per calcolare la riga 2 e continuare fino al completamento della riga n.

Tabella delle opzioni

Trace

Una volta completato B, concentrati su B[n][M], il valore totale ottimale su tutti gli n pacchetti con capacità M.

• If B[n][M] = B[n-1][M], il pacchetto n non è stato selezionato, quindi continua tracing da B[n-1][M].
• If B[n][M] ≠ B[n-1][M], il pacchetto n è stato selezionato, quindi continua tracing da B[n-1][M – W[n]].

Ripeti l'operazione finché non raggiungi la riga 0 della tabella.

Algoritmo per cercare la tabella delle opzioni per trovare i pacchetti selezionati

Nota: ogni volta che B[i][j] = B[i-1][j], il pacchetto i non è selezionato. Il valore B[n][M] è il valore totale ottimale da riporre nello zaino.

Passi per tracselezionando i pacchetti scelti:

• Passo 1: Inizia da i = n, j = M.
• Passo 2: Scansiona la colonna j dal basso verso l'alto finché non trovi una riga i in cui B[i][j] > B[i-1][j]. Contrassegna il pacchetto i come selezionato: Select[i] = true.
• Passo 3: Aggiorna j = j – W[i]. Se j > 0, torna al passaggio 2, altrimenti vai al passaggio 4.
• Passo 4: Stampare tutti i pacchetti contrassegnati come selezionati.

Java Code

Le seguenti Java il metodo riempie B[][] dal basso verso l'alto, stampa la tabella per l'ispezione e poi traces i pacchetti selezionati.

public void knapsackDyProg(int W[], int V[], int M, int n) {
    int B[][] = new int[n + 1][M + 1];

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= M; j++) {
            B[i][j] = 0;
        }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= M; j++) {
            B[i][j] = B[i - 1][j];

            if ((j >= W[i - 1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) {
                B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1];
            }

            System.out.print(B[i][j] + " ");
        }
        System.out.print("\n");
    }

    System.out.println("Max Value:\t" + B[n][M]);
    System.out.println("Selected Packs: ");

    int j = M;
    while (n != 0) {
        if (B[n][j] != B[n - 1][j]) {
            System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
            j = j - W[n - 1];
        }
        n--;
    }
}

Funzione zainoDyProg() in Java

Spiegazione del codice:

1. Assegna tabella B[][] e inizializzare ogni cella a 0.
2. Riempi B[][] dal basso verso l'alto utilizzando la relazione di ricorrenza della sezione precedente.
3. Inizia ogni cella con il valore “skip package i”. B[i-1][j].
4. Se la selezione del pacchetto i è fattibile e offre un valore nettamente migliore, sovrascrivi la cella.
5. Trace riporta gli elementi selezionati dalla riga n alla riga 0.
6. Ogniqualvolta viene scelto il pacchetto n, decrementa la capacità rimanente di W[n-1].

Nota di correzione: il parametro mutato del frammento originale M mentre continuavo a leggere B[n][M]La versione più sicura qui sopra utilizza un cursore separato. j per l' trace.

Migliori Java Il driver esegue l'algoritmo su due esempi pratici:

public void run() {
    // First Example
    // int W[] = new int[]{3, 4, 5, 9, 4};
    // int V[] = new int[]{3, 4, 4, 10, 4};
    // int M = 11;

    // Second Example
    int W[] = new int[]{12, 2, 1, 1, 4};
    int V[] = new int[]{4, 2, 1, 2, 10};
    int M = 15;

    int n = V.length;
    knapsackDyProg(W, V, M, n);
}

Output per il primo esempio:

0 0 0 3 3 3 3 3 3 3 3 3
0 0 0 3 4 4 4 7 7 7 7 7
0 0 0 3 4 4 4 7 7 8 8 8
0 0 0 3 4 4 4 7 7 10 10 10
0 0 0 3 4 4 4 7 8 10 10 11
Max Value:	11
Selected Packs:
	Package 5 with W = 4 and Value = 4
	Package 2 with W = 4 and Value = 4
	Package 1 with W = 3 and Value = 3

Output per il secondo esempio:

0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4
0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6
0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7
0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8
0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15
Max Value:	15
Selected Packs:
	Package 5 with W = 4 and Value = 10
	Package 4 with W = 1 and Value = 2
	Package 3 with W = 1 and Value = 1
	Package 2 with W = 2 and Value = 2

Complessità temporale e spaziale del problema dello zaino 0/1

• Complessità temporale: O(n · M) — i due cicli annidati fanno scorrere n elementi attraverso M+1 stati di capacità.
• Complessità spaziale: O(n · M) per la tabella completa, riducibile a O(M) tramite keeping solo la riga precedente quando tracNon è necessario il pagamento elettronico in contrassegno.

Il tempo di esecuzione è pseudo-polinomio: polinomiale nel valore di M ma esponenziale nei bit utilizzati per codificare M. Ecco perché il problema dello zaino 0/1 rimane NP-difficile anche se la programmazione dinamica è efficiente nella pratica.

Applicazioni del problema dello zaino 0/1

• Carico merci, imballaggio container e prelievo in magazzino nel rispetto dei limiti di peso.
• Allocazione del budget tra progetti di investimento con costi fissi e rendimento atteso.
• Problemi di taglio del materiale nella produzione che non consentono di separare i singoli pezzi.
• Schemi crittografici come Merkle-Hellman che si basano sulla difficoltà del problema dello zaino.
• Pianificazione con risorse limitate nel cloud computing e allocazione dei task della CPU.
• Selezione delle caratteristiche nell'apprendimento automatico con un budget di caratteristiche fisso.

DOMANDE FREQUENTI