Vai al contenuto

18.2 Un primo algoritmo di PD

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

  • Passo 1: calcolo del valore ottimo

    Per ogni \(k \in \{0,1,\dots,c\}\), sia \(v(k)\) il valore ottimo della sottoistanza dell'UKP data da:

    1. uno zaino di capacità \(k\),

    2. l'insieme \(\{1,2,\dots,n\}\) di \(n\) tipi di oggetto,

    3. per ogni tipo di oggetto \(j \in \{1,2,\dots,n\}\), un profitto \(p_j\) e un peso \(w_j\).

    La formula ricorsiva per calcolare \(v(k)\) è la seguente:

    \[\begin{equation*} \label{eq:ukp1} v(k)= \left\{ \begin{array}{ll} 0, & \textrm{se $k=0$,}\\[1ex] \displaystyle \max_{j \,:\, w_j\le k}\{p_j+v(k-w_j)\}, & \textrm{se $k\ge 1$ e $w_j\le k$ per qualche $j$,}\\[2ex] 0, & \textrm{se $k\ge 1$ e $w_j> k$ per ogni $j$.} \end{array} \right. \tag{18.1} \end{equation*}\]

    • Il processo di decomposizione ricorsiva della formula \(\eqref{eq:ukp1}\) genera al più \(n\) sottoproblemi indipendenti, ciascuno corrispondente a una possibile scelta di un tipo di oggetto \(j\), fra quelli con \(w_j\le k\), da inserire come uno degli oggetti dello zaino di capacità \(k\).

    • Il caso base è \(v(0)=0\), poiché uno zaino di capacità \(0\) non può contenere alcun oggetto e ha profitto \(0\). Inoltre, se \(w_j>k\) per ogni tipo di oggetto \(j\), nessun oggetto entra nello zaino: l'unica scelta ammissibile è non inserire alcun oggetto, e quindi \(v(k)=0\).

    • Il valore ottimo \(v(k)\) si ottiene provando ogni tipo di oggetto \(j\) con \(w_j\le k\) e scegliendo quello che massimizza la somma \(p_j+v(k-w_j)\) del profitto del tipo di oggetto scelto e del valore ottimo del sottoproblema residuo.

    • Poiché il tipo di oggetto \(j\) è disponibile in infinite copie, può essere scelto di nuovo anche nella soluzione del sottoproblema residuo di capacità \(k-w_j\).

    • Quindi una soluzione ottima per uno zaino di capacità \(k\) si costruisce combinando il tipo di oggetto \(j\) scelto con una soluzione ottima del sottoproblema residuo di capacità \(k-w_j\).

      \(\rightsquigarrow\) Sottostruttura ottima verificata!

    • Scelte diverse del primo tipo di oggetto, fatte eventualmente per valori diversi di \(k\), possono portare alla stessa capacità residua; quindi lo stesso valore \(v(k)\) può dover essere calcolato più volte durante la valutazione ricorsiva della formula \(\eqref{eq:ukp1}\).

      \(\rightsquigarrow\) Sottoproblemi sovrapposti verificati!

    • Un primo metodo per calcolare il valore ottimo \(v(c)\) dell'istanza dell'UKP è l'approccio top-down.

    • Il metodo parte dalla chiamata con \(k=c\) e valuta ricorsivamente la formula \(\eqref{eq:ukp1}\): ogni chiamata per uno zaino di capacità \(k\) genera altre chiamate per la capacità \(k-w_j\), per ogni tipo di oggetto \(j\) con \(w_j\le k\), finché si raggiunge il caso base \(v(0)\) o nessun tipo di oggetto entra nella capacità residua.

    • L'albero di ricorsione della funzione \(v\) ha un nodo per ogni chiamata ricorsiva, etichettato con la chiamata che rappresenta. La radice rappresenta la chiamata iniziale. I figli di un nodo rappresentano le chiamate ricorsive fatte da quella chiamata. Le foglie rappresentano i casi base.

      Esempio 18.2: Albero di ricorsione

      Consideriamo l'istanza dell'UKP dell'Esempio 18.1, con capacità \(c=7\) e tipi di oggetto di pesi \(w_1=2\), \(w_2=3\), \(w_3=5\), \(w_4=6\). Questo è l'albero di ricorsione dell'approccio top-down per calcolare \(v(7)\):

      Figura 1

      La funzione \(v\) viene chiamata \(15\) volte e gli stessi sottoproblemi vengono risolti più volte: \(v(2)\) viene chiamata \(3\) volte, \(v(1)\) viene chiamata \(3\) volte e \(v(0)\) viene chiamata \(5\) volte. Tutte le altre chiamate avvengono una sola volta.

    • Il valore \(v(k)\), per una capacità generica \(k\), si può calcolare quando sono noti i valori \(v(k')\) per tutte le capacità più piccole \(k'<k\).

      Esempio 18.3: Calcolo dei valori della funzione \(v\)

      Consideriamo l'istanza dell'UKP dell'Esempio 18.1, con uno zaino di capacità \(c=7\) e 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} \]

      Il valore della funzione \(v\) si può calcolare partendo dal caso base \(v(0)=0\) e calcolando poi in ordine i valori \(v(1),v(2),\dots,v(7)\), come segue:

      • Poiché nessun tipo di oggetto ha \(w_j\le 1\), abbiamo:

        \[ v(1)=0. \]

      • Calcolato \(v(0)\), possiamo calcolare \(v(2)\) come segue:

        \[ v(2)=p_1+v(0)=4+0=4. \]

      • Calcolati \(v(1)\) e \(v(0)\), possiamo calcolare \(v(3)\) come segue:

        \[ v(3)=\max\{p_1+v(1),p_2+v(0)\}=\max\{4+0,5+0\}=5. \]

      • Calcolati \(v(2)\) e \(v(1)\), possiamo calcolare \(v(4)\) come segue:

        \[ v(4)=\max\{p_1+v(2),p_2+v(1)\}=\max\{4+4,5+0\}=8. \]

      • Calcolati \(v(3)\), \(v(2)\) e \(v(0)\), possiamo calcolare \(v(5)\) come segue:

        \[ v(5)=\max\{p_1+v(3),p_2+v(2),p_3+v(0)\}=\max\{4+5,5+4,10+0\}=10. \]

      • Calcolati \(v(4)\), \(v(3)\), \(v(1)\) e \(v(0)\), possiamo calcolare \(v(6)\) come segue:

        \[\begin{align*} v(6)&=\max\{p_1+v(4),p_2+v(3),p_3+v(1),p_4+v(0)\}\\ &=\max\{4+8,5+5,10+0,11+0\}=12. \end{align*}\]

      • Calcolati \(v(5)\), \(v(4)\), \(v(2)\) e \(v(1)\), possiamo calcolare \(v(7)\) come segue:

        \[\begin{align*} v(7)&=\max\{p_1+v(5),p_2+v(4),p_3+v(2),p_4+v(1)\}\\ &=\max\{4+10,5+8,10+4,11+0\}=14. \end{align*}\]

    • Possiamo evitare di risolvere ripetutamente gli stessi sottoproblemi memorizzando il valore di ogni sottoproblema appena calcolato. I valori sono memorizzati in una lookup table.

    • Poiché la soluzione di un sottoproblema di valore \(v(k)\) dipende solo da sottoproblemi di valori \(v(k')\), con \(k'<k\), possiamo risolvere i sottoproblemi per valori crescenti di \(k\), partendo dal caso base \(v(0)=0\) fino ad arrivare a \(v(c)\).

    • Questa osservazione porta in modo naturale a un metodo molto più efficiente per calcolare il valore ottimo \(v(c)\) dell'istanza dell'UKP.

    • Un secondo metodo per calcolare il valore ottimo \(v(c)\) dell'istanza dell'UKP è l'approccio bottom-up.

    • Il metodo parte dal caso base \(v(0)=0\) e valuta la formula \(\eqref{eq:ukp1}\) per capacità crescenti \(k \in \{1,2,\dots,c\}\): ogni valore \(v(k)\) si calcola con i valori già calcolati \(v(0),v(1),\dots,v(k-1)\), fino a ottenere il valore \(v(c)\) dell'istanza dell'UKP.

      Questo è lo pseudocodice dell'algoritmo di PD con l'approccio bottom-up:

      Algoritmo: UKP_DP1

      Input: Un'istanza dell'UKP data da \(n\), dai vettori \(p[1..n]\), \(w[1..n]\) e dalla capacità \(c\)
      Output: Il valore ottimo dell'istanza dell'UKP
      1Function UKP_DP1(\(n,p,w,c\))
      2\(v := \textnormal{new array}[0..c]\)
      3\(v[0] \leftarrow 0\)
      4for \(k := 1\) to \(c\) do
      5\(m := 0\)
      6for \(j := 1\) to \(n\) do
      7if \(w[j] \le k\) then
      8if \(p[j]+v[k-w[j]] > m\) then
      9\(m \leftarrow p[j]+v[k-w[j]]\)
      10end
      11end
      12end
      13\(v[k] \leftarrow m\)
      14end
      15return \(v[c]\)

      • Il vettore \(v[0..c]\) è la lookup table: memorizza i valori ottimi di tutti i sottoproblemi, con il caso base \(v[0]=0\).

      • Il ciclo esterno, su \(k \in \{1,2,\dots,c\}\), calcola \(v[k]\) in ordine crescente di capacità.

      • Il ciclo interno, su \(j \in \{1,2,\dots,n\}\), esamina ogni tipo di oggetto; la condizione \(w[j]\le k\) verifica se il tipo di oggetto \(j\) entra nella capacità \(k\), e in \(m\) si tiene il valore \(p[j]+v[k-w[j]]\) più grande trovato finora. Se nessun tipo di oggetto entra, \(m\) resta uguale al suo valore iniziale \(0\).

      • Al termine del ciclo interno, \(v[k] \leftarrow m\) memorizza il valore ottimo \(v[k]\).

      • Infine, l'algoritmo restituisce il valore ottimo \(v[c]\) dell'istanza dell'UKP.

      Esempio 18.4: Esecuzione dell'algoritmo di PD

      Consideriamo l'istanza dell'UKP dell'Esempio 18.1, con uno zaino di capacità \(c=7\) e 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} \]

      Per ogni passo dell'algoritmo di PD, la tabella riporta i valori di \(k\) e \(j\), il valore corrente di \(m\) e la cella \(v[k]\). La cella di \(m\) è evidenziata in rosso quando viene aggiornata; la cella di \(v[k]\) è evidenziata in blu quando viene assegnata.

      \(k\) \(j\) \(v[k]\) \(m\) Azione
      \(-\) \(-\) 0 \(-\) \(v[0]\leftarrow 0\)
      \(-\) \(-\) 0 \(m := 0\)
      1 1 \(-\) 0 \(w[1]=2>1\): saltare
      2 \(-\) 0 \(w[2]=3>1\): saltare
      3 \(-\) 0 \(w[3]=5>1\): saltare
      4 \(-\) 0 \(w[4]=6>1\): saltare
      \(-\) 0 0 \(v[1]\leftarrow m=0\)
      \(-\) \(-\) 0 \(m := 0\)
      2 1 \(-\) 4 \(p[1]{+}v[0]=4{+}0=4>m=0\): \(m\leftarrow 4\)
      2 \(-\) 4 \(w[2]=3>2\): saltare
      3 \(-\) 4 \(w[3]=5>2\): saltare
      4 \(-\) 4 \(w[4]=6>2\): saltare
      \(-\) 4 4 \(v[2]\leftarrow m=4\)
      \(-\) \(-\) 0 \(m := 0\)
      3 1 \(-\) 4 \(p[1]{+}v[1]=4{+}0=4>m=0\): \(m\leftarrow 4\)
      2 \(-\) 5 \(p[2]{+}v[0]=5{+}0=5>m=4\): \(m\leftarrow 5\)
      3 \(-\) 5 \(w[3]=5>3\): saltare
      4 \(-\) 5 \(w[4]=6>3\): saltare
      \(-\) 5 5 \(v[3]\leftarrow m=5\)
      \(-\) \(-\) 0 \(m := 0\)
      4 1 \(-\) 8 \(p[1]{+}v[2]=4{+}4=8>m=0\): \(m\leftarrow 8\)
      2 \(-\) 8 \(p[2]{+}v[1]=5{+}0=5\le m=8\): nessun aggiornamento
      3 \(-\) 8 \(w[3]=5>4\): saltare
      4 \(-\) 8 \(w[4]=6>4\): saltare
      \(-\) 8 8 \(v[4]\leftarrow m=8\)
      \(-\) \(-\) 0 \(m := 0\)
      5 1 \(-\) 9 \(p[1]{+}v[3]=4{+}5=9>m=0\): \(m\leftarrow 9\)
      2 \(-\) 9 \(p[2]{+}v[2]=5{+}4=9=m\): nessun aggiornamento
      3 \(-\) 10 \(p[3]{+}v[0]=10{+}0=10>m=9\): \(m\leftarrow 10\)
      4 \(-\) 10 \(w[4]=6>5\): saltare
      \(-\) 10 10 \(v[5]\leftarrow m=10\)

      \(k\) \(j\) \(v[k]\) \(m\) Azione
      \(-\) \(-\) 0 \(m := 0\)
      6 1 \(-\) 12 \(p[1]{+}v[4]=4{+}8=12>m=0\): \(m\leftarrow 12\)
      2 \(-\) 12 \(p[2]{+}v[3]=5{+}5=10\le m=12\): nessun aggiornamento
      3 \(-\) 12 \(p[3]{+}v[1]=10{+}0=10\le m=12\): nessun aggiornamento
      4 \(-\) 12 \(p[4]{+}v[0]=11{+}0=11\le m=12\): nessun aggiornamento
      \(-\) 12 12 \(v[6]\leftarrow m=12\)
      \(-\) \(-\) 0 \(m := 0\)
      7 1 \(-\) 14 \(p[1]{+}v[5]=4{+}10=14>m=0\): \(m\leftarrow 14\)
      2 \(-\) 14 \(p[2]{+}v[4]=5{+}8=13\le m=14\): nessun aggiornamento
      3 \(-\) 14 \(p[3]{+}v[2]=10{+}4=14=m\): nessun aggiornamento
      4 \(-\) 14 \(p[4]{+}v[1]=11{+}0=11\le m=14\): nessun aggiornamento
      \(-\) 14 14 \(v[7]\leftarrow m=14\)

      Questo è il vettore \(v\) dopo l'esecuzione dell'algoritmo di PD:

      \[ \begin{array}{c|cccccccc} \hline & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} \\ \hline {v[k]} & 0 & 0 & 4 & 5 & 8 & 10 & 12 & 14 \\ \hline \end{array} \]

    • Dopo l'esecuzione dell'algoritmo di PD, il vettore \(v\) contiene il valore ottimo \(v[k]\) per ogni capacità.

  • Passo 2: calcolo di una soluzione ottima

    • Per calcolare una soluzione ottima è necessario memorizzare alcune informazioni aggiuntive.

    • Per ogni capacità \(k\), oltre al valore ottimo \(v[k]\), memorizziamo \(s[k]\), il tipo di oggetto selezionato come primo oggetto in una soluzione ottima per uno zaino di capacità \(k\); se nessun tipo di oggetto entra nella capacità \(k\), poniamo \(s[k]=0\).

    • Partendo da \(k=c\), il valore \(s[k]\) dà il tipo del primo oggetto selezionato; la capacità residua diventa \(k-w_{s[k]}\) e si può applicare di nuovo la stessa regola, e così via, finché la capacità residua arriva a \(0\) o nessun tipo di oggetto vi entra (\(s[k]=0\)); in questo caso la capacità residua resta inutilizzata.

      Questo è lo pseudocodice dell'algoritmo di PD con l'approccio bottom-up, con la memorizzazione delle informazioni necessarie per calcolare una soluzione ottima:

      Algoritmo: UKP_DP1_InfoSol

      Input: Un'istanza dell'UKP data da \(n\), dai vettori \(p[1..n]\), \(w[1..n]\) e dalla capacità \(c\)
      Output: Il valore ottimo dell'istanza dell'UKP e il vettore delle informazioni \(s[0..c]\)
      1Function UKP_DP1_InfoSol(\(n,p,w,c\))
      2\(v := \textnormal{new array}[0..c]\); \(s := \textnormal{new array}[0..c]\)
      3\(v[0] \leftarrow 0\); \(s[0] \leftarrow 0\)
      4for \(k := 1\) to \(c\) do
      5\(m := 0\); \(t := 0\)
      6for \(j := 1\) to \(n\) do
      7if \(w[j] \le k\) then
      8if \(p[j]+v[k-w[j]] > m\) then
      9\(m \leftarrow p[j]+v[k-w[j]]\); \(t \leftarrow j\)
      10end
      11end
      12end
      13\(v[k] \leftarrow m\); \(s[k] \leftarrow t\)
      14end
      15return \(v[c],s\)

      • L'algoritmo di PD usa la variabile temporanea aggiuntiva \(t\) per registrare la decisione presa quando \(m\) viene aggiornato. Se il tipo di oggetto \(j\) è selezionato, \(t\leftarrow j\) memorizza questa decisione; se nessun tipo di oggetto entra nella capacità \(k\), \(t\) mantiene il suo valore iniziale \(0\).

      • Al termine del ciclo interno, \(s[k]\leftarrow t\) memorizza il tipo di oggetto selezionato, insieme al valore ottimo \(v[k]\leftarrow m\).

      Esempio 18.5: Calcolo delle informazioni aggiuntive

      Consideriamo l'istanza dell'UKP dell'Esempio 18.1, con uno zaino di capacità \(c=7\) e 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} \]

      Per ogni passo dell'algoritmo di PD, la tabella riporta i valori di \(k\) e \(j\), la cella \(s[k]\), il valore corrente di \(m\) e il valore corrente di \(t\). La cella di \(m\) è evidenziata in rosso quando viene aggiornata; la cella di \(t\) e la cella di \(s[k]\) sono evidenziate in blu quando vengono aggiornate.

      \(k\) \(j\) \(s[k]\) \(m\) \(t\) Azione
      \(-\) \(-\) \(-\) \(-\) \(-\) Stato iniziale: \(v[0]\leftarrow 0\), \(s[0]\leftarrow 0\)
      \(-\) \(-\) 0 0 \(m := 0\), \(t := 0\)
      1 1 \(-\) 0 0 \(w[1]=2>1\): saltare
      2 \(-\) 0 0 \(w[2]=3>1\): saltare
      3 \(-\) 0 0 \(w[3]=5>1\): saltare
      4 \(-\) 0 0 \(w[4]=6>1\): saltare
      \(-\) 0 0 0 \(v[1]\leftarrow m=0\), \(s[1]\leftarrow t=0\)
      \(-\) \(-\) 0 0 \(m := 0\), \(t := 0\)
      2 1 \(-\) 4 1 \(4{+}0=4>m=0\): \(m\leftarrow 4\), \(t\leftarrow 1\)
      2 \(-\) 4 1 \(w[2]=3>2\): saltare
      3 \(-\) 4 1 \(w[3]=5>2\): saltare
      4 \(-\) 4 1 \(w[4]=6>2\): saltare
      \(-\) 1 4 1 \(v[2]\leftarrow m=4\), \(s[2]\leftarrow t=1\)
      \(-\) \(-\) 0 0 \(m := 0\), \(t := 0\)
      3 1 \(-\) 4 1 \(4{+}0=4>m=0\): \(m\leftarrow 4\), \(t\leftarrow 1\)
      2 \(-\) 5 2 \(5{+}0=5>m=4\): \(m\leftarrow 5\), \(t\leftarrow 2\)
      3 \(-\) 5 2 \(w[3]=5>3\): saltare
      4 \(-\) 5 2 \(w[4]=6>3\): saltare
      \(-\) 2 5 2 \(v[3]\leftarrow m=5\), \(s[3]\leftarrow t=2\)
      \(-\) \(-\) 0 0 \(m := 0\), \(t := 0\)
      4 1 \(-\) 8 1 \(4{+}4=8>m=0\): \(m\leftarrow 8\), \(t\leftarrow 1\)
      2 \(-\) 8 1 \(5{+}0=5\le m=8\): nessun aggiornamento
      3 \(-\) 8 1 \(w[3]=5>4\): saltare
      4 \(-\) 8 1 \(w[4]=6>4\): saltare
      \(-\) 1 8 1 \(v[4]\leftarrow m=8\), \(s[4]\leftarrow t=1\)
      \(-\) \(-\) 0 0 \(m := 0\), \(t := 0\)
      5 1 \(-\) 9 1 \(4{+}5=9>m=0\): \(m\leftarrow 9\), \(t\leftarrow 1\)
      2 \(-\) 9 1 \(5{+}4=9=m\): nessun aggiornamento
      3 \(-\) 10 3 \(10{+}0=10>m=9\): \(m\leftarrow 10\), \(t\leftarrow 3\)
      4 \(-\) 10 3 \(w[4]=6>5\): saltare
      \(-\) 3 10 3 \(v[5]\leftarrow m=10\), \(s[5]\leftarrow t=3\)

      \(k\) \(j\) \(s[k]\) \(m\) \(t\) Azione
      \(-\) \(-\) 0 0 \(m := 0\), \(t := 0\)
      6 1 \(-\) 12 1 \(4{+}8=12>m=0\): \(m\leftarrow 12\), \(t\leftarrow 1\)
      2 \(-\) 12 1 \(5{+}5=10\le m=12\): nessun aggiornamento
      3 \(-\) 12 1 \(10{+}0=10\le m=12\): nessun aggiornamento
      4 \(-\) 12 1 \(11{+}0=11\le m=12\): nessun aggiornamento
      \(-\) 1 12 1 \(v[6]\leftarrow m=12\), \(s[6]\leftarrow t=1\)
      \(-\) \(-\) 0 0 \(m := 0\), \(t := 0\)
      7 1 \(-\) 14 1 \(4{+}10=14>m=0\): \(m\leftarrow 14\), \(t\leftarrow 1\)
      2 \(-\) 14 1 \(5{+}8=13\le m=14\): nessun aggiornamento
      3 \(-\) 14 1 \(10{+}4=14=m\): nessun aggiornamento
      4 \(-\) 14 1 \(11{+}0=11\le m=14\): nessun aggiornamento
      \(-\) 1 14 1 \(v[7]\leftarrow m=14\), \(s[7]\leftarrow t=1\)

      Questo è il vettore \(s\) dopo l'esecuzione dell'algoritmo di PD:

      \[ \begin{array}{c|cccccccc} \hline & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} \\ \hline {s[k]} & 0 & 0 & 1 & 2 & 1 & 3 & 1 & 1 \\ \hline \end{array} \]

    • Calcolato il vettore \(s\), si può calcolare una soluzione ottima dell'istanza dell'UKP applicando ripetutamente la seguente regola, partendo da \(k=c\) e da \(x_j=0\) per ogni \(j \in \{1,2,\dots,n\}\):

      \[ x_{s[k]} \leftarrow x_{s[k]}+1, \qquad k \leftarrow k-w_{s[k]}, \]

      finché \(k=0\) o \(s[k]=0\). Il secondo caso si verifica quando nessun tipo di oggetto entra nella capacità residua \(k\), che resta quindi inutilizzata. Si ottiene così il vettore \((x_1,x_2,\dots,x_n)\), dove ogni componente \(x_j\) è il numero di copie del tipo di oggetto \(j\) in una soluzione ottima.

    • Il seguente pseudocodice realizza il calcolo di una soluzione ottima, dato il vettore \(s\).

      Algoritmo: UKP_DP1_SolComputation

      Input: Il numero \(n\) di tipi di oggetto, la capacità \(c\), il vettore \(w[1..n]\) e il vettore \(s[0..c]\)
      Output: Una soluzione ottima dell'istanza dell'UKP
      1Function UKP_DP1_SolComputation(\(n,w,c,s\))
      2\(x := \textnormal{new array}[1..n]\)
      3for \(j := 1\) to \(n\) do
      4\(x[j] \leftarrow 0\)
      5end
      6\(k := c\)
      7while \(k > 0\) e \(s[k] > 0\) do
      8\(x[s[k]] \leftarrow x[s[k]]+1\)
      9\(k \leftarrow k - w[s[k]]\)
      10end
      11return \(x\)

      Esempio 18.6: Calcolo di una soluzione ottima

      Dopo l'esecuzione dell'algoritmo di PD sull'istanza dell'Esempio 18.1, abbiamo il seguente vettore \(s\):

      \[ \begin{array}{c|cccccccc} \hline & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} \\ \hline {s[k]} & 0 & 0 & 1 & 2 & 1 & 3 & 1 & 1 \\ \hline \end{array} \]

      Possiamo calcolare una soluzione ottima per uno zaino di capacità \(c=7\) come segue:

      Iterazione \(k\) \(s[k]\) \(x[1]\) \(x[2]\) \(x[3]\) \(x[4]\) \(k \leftarrow k-w_{s[k]}\)
      \(-\) \(-\) \(-\) 0 0 0 0 \(k=7\)
      \(1\) \(7\) \(1\) 1 0 0 0 \(k=7-2=5\)
      \(2\) \(5\) \(3\) 1 0 1 0 \(k=5-5=0\)

      Una soluzione ottima è il vettore:

      \[ (1,0,1,0) \]

      Il suo peso totale è \(w_1+w_3=2+5=7=c\) e il suo profitto totale è \(p_1+p_3=4+10=14\), che coincide con il valore ottimo \(v(7)=14\).

18.2.1 Numero di passi

  • Indichiamo con \(S(n,c)\) il numero di passi eseguiti da UKP_DP1 nel caso peggiore, dove \(n\) è il numero di tipi di oggetto e \(c\) è la capacità dello zaino. Calcoliamo \(S(n,c)\) contando quante volte vengono eseguite le righe dello pseudocodice di UKP_DP1.

  • Nel caso peggiore, le condizioni delle righe 7 e 8 sono vere a ogni iterazione del ciclo interno, e quindi la riga 9 viene eseguita tante volte quanto la riga 8. Il numero di esecuzioni delle righe rilevanti è:

    • La Riga 2 viene eseguita \(1\) volta.

    • La Riga 3 viene eseguita \(1\) volta.

    • La Riga 4 viene eseguita \(c\) volte.

    • La Riga 5 viene eseguita \(c\) volte.

    • La Riga 6 viene eseguita \(cn\) volte.

    • La Riga 7 viene eseguita \(cn\) volte.

    • La Riga 8 viene eseguita \(cn\) volte.

    • La Riga 9 viene eseguita \(cn\) volte.

    • La Riga 13 viene eseguita \(c\) volte.

    • La Riga 15 viene eseguita \(1\) volta.

    Pertanto, il numero totale di passi nel caso peggiore è

    \[ 1+1+c+c+cn+cn+cn+cn+c+1. \]

    Quindi

    \[ S(n,c)=3+3c+4cn. \]

    Dunque

    \[ S(n,c)=\Theta(nc). \]

    Infatti

    \[ \lim_{n,c\to\infty} \frac{4cn+3c+3}{nc} = \lim_{n,c\to\infty} \left(4+\frac{3}{n}+\frac{3}{nc}\right) = 4\in\mathbb{R}_{>0}. \]

    L'algoritmo di PD esegue

    \[ S(n,c)=\Theta(nc) \]

    passi nel caso peggiore.

  • La versione UKP_DP1_InfoSol memorizza il vettore aggiuntivo \(s\) ed esegue solo un numero costante di operazioni in più dentro gli stessi cicli. Pertanto, il suo numero di passi resta \(\Theta(nc)\).

Avanti: 18.3 Un secondo algoritmo di PD