Vai al contenuto

PD per il problema dello zaino illimitato

Parte 3 · Programmazione dinamica · Capitolo 18 · Dispensa, volume 3 (PDF) · Slide · Esercizi: Zaino illimitato (UKP) · App: Tabelle della PD per i problemi di zaino

Prerequisiti

Obiettivi

Al termine di questo capitolo saremo in grado di:

  • spiegare perché l'UKP differisce dal problema dello zaino 0/1 (KP) e scrivere la ricorrenza \(v(k)\) sulle sole capacità;

  • eseguire a mano l'algoritmo di PD sulle capacità e sulle coppie (tipo di oggetto, capacità);

  • ricostruire una soluzione ottima, compreso il caso in cui una parte della capacità resta inutilizzata;

  • contare i passi dei due algoritmi di PD e confrontarli.

Il problema di questo capitolo è il problema dello zaino illimitato (UKP): la sua definizione e le sue ipotesi sono nella sua pagina.

18.1 Istanze e soluzioni ammissibili

Esempio 18.1: Istanza dell'UKP

Consideriamo uno zaino di capacità \(c=7\) e \(4\) tipi di oggetto, con i seguenti profitti e pesi:

\[ \begin{array}{l|rrrr} \hline & {j=1} & {j=2} & {j=3} & {j=4} \\ \hline {p_j} & 4 & 5 & 10 & 11 \\ {w_j} & 2 & 3 & 5 & 6 \\ \hline \end{array} \]

Chiamiamo questa istanza dell'UKP Esempio 18.1.

Per ogni tipo di oggetto \(j\), una soluzione ammissibile può usare al più \(\lfloor c/w_j \rfloor\) copie del tipo di oggetto \(j\), poiché con più copie si supererebbe la capacità \(c\) già con il solo tipo di oggetto \(j\). Di conseguenza, il numero di soluzioni ammissibili è al più \(\prod_{j=1}^{n}\big(\lfloor c/w_j \rfloor+1\big)\).

  • Il numero di possibili soluzioni dell'UKP cresce rapidamente con il numero \(n\) di tipi di oggetto e con la capacità \(c\), poiché ogni variabile \(x_j\) può assumere in modo indipendente uno qualsiasi di \(\lfloor c/w_j \rfloor+1\) valori. Pertanto, l'enumerazione di tutte le possibili soluzioni diventa presto impraticabile al crescere di \(n\) o di \(c\).

18.1.1 Codifica delle soluzioni ammissibili

Una soluzione ammissibile è descritta dal vettore intero

\[ (x_1,x_2,\dots,x_n), \]

dove \(x_j\in\Z_{\ge 0}\) è il numero di copie selezionate del tipo di oggetto \(j\). La soluzione è ammissibile se

\[ \sum_{j=1}^{n} w_j x_j \le c. \]

Il suo profitto totale è

\[ \sum_{j=1}^{n} p_j x_j. \]

La differenza principale rispetto al KP è che le variabili non sono più binarie. Nell'UKP ogni variabile \(x_j\) può assumere qualunque valore intero non negativo, purché il vincolo di capacità sia rispettato.

  • Panoramica

    Istanze e soluzioni ammissibili · Codifica delle soluzioni ammissibili

    Apri

  • 18.2 Un primo algoritmo di PD

    Apri

  • 18.3 Un secondo algoritmo di PD

    Apri

  • Errori tipici · In sintesi

    In sintesi

    Apri

Avanti: 18.2 Un primo algoritmo di PD

Esercizi su questo capitolo: Zaino illimitato (UKP)

Nel laboratorio interattivo: Tabelle della PD per i problemi di zaino.