Esercizi · PD per il problema del cambio monete

Esercizi · Capitolo 27 · ogni soluzione si apre con un clic · Capitolo 27: Cambio monete (CCP) · Eserciziario, volume 3 (PDF)

Esercizio 27.1: Esercizio 1: problema del cambio monete

Consideriamo la seguente istanza del CCP, in cui il resto da restituire è \(c=6\) e i tagli sono

\[ w=(1,4). \]

Domande

1. Mostrare l'esecuzione dell'algoritmo di PD bottom-up riportando, per ogni iterazione, i valori dell'array \(v\) e dell'array \(s\).

2. Usando l'array \(s\), ricostruire una soluzione ottima in notazione intera \((x_1,x_2)\) e riportare il valore ottimo.

Soluzione

1. Esecuzione passo per passo dell'algoritmo di PD bottom-up

   Per ogni passo dell'algoritmo di PD, la tabella riporta il resto \(k\), le celle \(v[k]\) e \(s[k]\) e l'operazione eseguita; \(s[k]\) è l'indice \(j\) del taglio della moneta usata. In caso di pareggio si tiene l'indice minimo, perché \(m\) viene aggiornato solo quando il valore è strettamente minore.

   \(k\)	\(v[k]\)	\(s[k]\)	Azione
   0	0	0	\(v[0]\leftarrow 0\), \(s[0]\leftarrow 0\)
   1	1	1	\(\min\{1+v[0]\}=\min\{1\}=1\)
   2	2	1	\(\min\{1+v[1]\}=\min\{2\}=2\)
   3	3	1	\(\min\{1+v[2]\}=\min\{3\}=3\)
   4	1	2	\(\min\{1+v[3],\,1+v[0]\}=\min\{4,1\}=1\)
   5	2	1	\(\min\{1+v[4],\,1+v[1]\}=\min\{2,2\}=2\)
   6	3	1	\(\min\{1+v[5],\,1+v[2]\}=\min\{3,3\}=3\)

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

   \[ \begin{array}{l|rrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline {v[k]} & 0 & 1 & 2 & 3 & 1 & 2 & 3 \\ \hline \end{array} \]

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

   \[ \begin{array}{l|rrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline {s[k]} & 0 & 1 & 1 & 1 & 2 & 1 & 1 \\ \hline \end{array} \]

2. Abbiamo il seguente array \(s\):

   \[ \begin{array}{l|rrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline {s[k]} & 0 & 1 & 1 & 1 & 2 & 1 & 1 \\ \hline \end{array} \]

   Possiamo ricostruire una soluzione ottima partendo da \(k=6\) come segue:

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

   Quindi il vettore

   \[ (2,1) \]

   è una soluzione ottima: il suo valore totale è \(2\cdot1+1\cdot4=6=c\). Il valore ottimo è

   \[ v[6]=3. \]

Esercizio 27.2: Esercizio 2: problema del cambio monete

Consideriamo la seguente istanza del CCP, in cui il resto da restituire è \(c=11\) e i tagli sono

\[ w=(3,5). \]

Domande

1. Mostrare l'esecuzione dell'algoritmo di PD bottom-up riportando, per ogni iterazione, i valori dell'array \(v\) e dell'array \(s\).

2. Usando l'array \(s\), ricostruire una soluzione ottima in notazione intera \((x_1,x_2)\) e riportare il valore ottimo.

Soluzione

1. Esecuzione passo per passo dell'algoritmo di PD bottom-up

   Per ogni passo dell'algoritmo di PD, la tabella riporta il resto \(k\), le celle \(v[k]\) e \(s[k]\) e l'operazione eseguita; \(s[k]\) è l'indice \(j\) del taglio della moneta usata. In caso di pareggio si tiene l'indice minimo, perché \(m\) viene aggiornato solo quando il valore è strettamente minore. Il valore \(+\infty\) indica un resto che non si può restituire, per il quale \(s[k]=0\).

   \(k\)	\(v[k]\)	\(s[k]\)	Azione
   0	0	0	\(v[0]\leftarrow 0\), \(s[0]\leftarrow 0\)
   1	\(+\infty\)	0	nessun taglio \(w_j\le 1\): \(v[1]\leftarrow +\infty\)
   2	\(+\infty\)	0	nessun taglio \(w_j\le 2\): \(v[2]\leftarrow +\infty\)
   3	1	1	\(\min\{1+v[0]\}=\min\{1\}=1\)
   4	\(+\infty\)	0	\(\min\{1+v[1]\}=\min\{+\infty\}=+\infty\)
   5	1	2	\(\min\{1+v[2],\,1+v[0]\}=\min\{+\infty,1\}=1\)
   6	2	1	\(\min\{1+v[3],\,1+v[1]\}=\min\{2,+\infty\}=2\)
   7	\(+\infty\)	0	\(\min\{1+v[4],\,1+v[2]\}=\min\{+\infty,+\infty\}=+\infty\)
   8	2	1	\(\min\{1+v[5],\,1+v[3]\}=\min\{2,2\}=2\)
   9	3	1	\(\min\{1+v[6],\,1+v[4]\}=\min\{3,+\infty\}=3\)
   10	2	2	\(\min\{1+v[7],\,1+v[5]\}=\min\{+\infty,2\}=2\)
   11	3	1	\(\min\{1+v[8],\,1+v[6]\}=\min\{3,3\}=3\)

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

   \[ \begin{array}{l|rrrrrrrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline {v[k]} & 0 & {+\infty} & {+\infty} & 1 & {+\infty} & 1 & 2 & {+\infty} & 2 & 3 & 2 & 3 \\ \hline \end{array} \]

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

   \[ \begin{array}{l|rrrrrrrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline {s[k]} & 0 & 0 & 0 & 1 & 0 & 2 & 1 & 0 & 1 & 1 & 2 & 1 \\ \hline \end{array} \]

2. Abbiamo il seguente array \(s\):

   \[ \begin{array}{l|rrrrrrrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline {s[k]} & 0 & 0 & 0 & 1 & 0 & 2 & 1 & 0 & 1 & 1 & 2 & 1 \\ \hline \end{array} \]

   Possiamo ricostruire una soluzione ottima partendo da \(k=11\) come segue:

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

   Quindi il vettore

   \[ (2,1) \]

   è una soluzione ottima: il suo valore totale è \(2\cdot3+1\cdot5=11=c\). Il valore ottimo è

   \[ v[11]=3. \]

Esercizio 27.3: Esercizio 3: problema del cambio monete

Consideriamo la seguente istanza del CCP, in cui il resto da restituire è \(c=7\) e i tagli sono

\[ w=(2,4). \]

Domande

1. Mostrare l'esecuzione dell'algoritmo di PD bottom-up riportando, per ogni iterazione, i valori dell'array \(v\) e dell'array \(s\).

2. Usando l'array \(s\), ricostruire una soluzione ottima in notazione intera \((x_1,x_2)\), oppure spiegare perché l'istanza è inammissibile, e riportare il valore ottimo.

Soluzione

1. Esecuzione passo per passo dell'algoritmo di PD bottom-up

   Per ogni passo dell'algoritmo di PD, la tabella riporta il resto \(k\), le celle \(v[k]\) e \(s[k]\) e l'operazione eseguita; \(s[k]\) è l'indice \(j\) del taglio della moneta usata. In caso di pareggio si tiene l'indice minimo, perché \(m\) viene aggiornato solo quando il valore è strettamente minore. Il valore \(+\infty\) indica un resto che non si può restituire, per il quale \(s[k]=0\).

   \(k\)	\(v[k]\)	\(s[k]\)	Azione
   0	0	0	\(v[0]\leftarrow 0\), \(s[0]\leftarrow 0\)
   1	\(+\infty\)	0	nessun taglio \(w_j\le 1\): \(v[1]\leftarrow +\infty\)
   2	1	1	\(\min\{1+v[0]\}=\min\{1\}=1\)
   3	\(+\infty\)	0	\(\min\{1+v[1]\}=\min\{+\infty\}=+\infty\)
   4	1	2	\(\min\{1+v[2],\,1+v[0]\}=\min\{2,1\}=1\)
   5	\(+\infty\)	0	\(\min\{1+v[3],\,1+v[1]\}=\min\{+\infty,+\infty\}=+\infty\)
   6	2	1	\(\min\{1+v[4],\,1+v[2]\}=\min\{2,2\}=2\)
   7	\(+\infty\)	0	\(\min\{1+v[5],\,1+v[3]\}=\min\{+\infty,+\infty\}=+\infty\)

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

   \[ \begin{array}{l|rrrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline {v[k]} & 0 & {+\infty} & 1 & {+\infty} & 1 & {+\infty} & 2 & {+\infty} \\ \hline \end{array} \]

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

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

2. Poiché \(v[7]=+\infty\), l'istanza è inammissibile: nessuna combinazione di monete dei tagli \(w=(2,4)\) restituisce un resto esattamente uguale a \(c=7\). Infatti ogni taglio è pari, quindi ogni resto che si può restituire è pari, mentre \(c=7\) è dispari.

   Poiché \(s[7]=0\), non c'è alcuna soluzione da ricostruire. Il valore ottimo è

   \[ v[7]=+\infty. \]

Esercizio 27.4: Esercizio 4: problema del cambio monete

Consideriamo la seguente istanza del CCP, in cui il resto da restituire è \(c=12\) e i tagli sono

\[ w=(3,7). \]

Domande

1. Mostrare l'esecuzione dell'algoritmo di PD bottom-up riportando, per ogni iterazione, i valori dell'array \(v\) e dell'array \(s\).

2. Usando l'array \(s\), ricostruire una soluzione ottima in notazione intera \((x_1,x_2)\) e riportare il valore ottimo.

Soluzione

1. Esecuzione passo per passo dell'algoritmo di PD bottom-up

   Per ogni passo dell'algoritmo di PD, la tabella riporta il resto \(k\), le celle \(v[k]\) e \(s[k]\) e l'operazione eseguita; \(s[k]\) è l'indice \(j\) del taglio della moneta usata. In caso di pareggio si tiene l'indice minimo, perché \(m\) viene aggiornato solo quando il valore è strettamente minore. Il valore \(+\infty\) indica un resto che non si può restituire, per il quale \(s[k]=0\).

   \(k\)	\(v[k]\)	\(s[k]\)	Azione
   0	0	0	\(v[0]\leftarrow 0\), \(s[0]\leftarrow 0\)
   1	\(+\infty\)	0	nessun taglio \(w_j\le 1\): \(v[1]\leftarrow +\infty\)
   2	\(+\infty\)	0	nessun taglio \(w_j\le 2\): \(v[2]\leftarrow +\infty\)
   3	1	1	\(\min\{1+v[0]\}=\min\{1\}=1\)
   4	\(+\infty\)	0	\(\min\{1+v[1]\}=\min\{+\infty\}=+\infty\)
   5	\(+\infty\)	0	\(\min\{1+v[2]\}=\min\{+\infty\}=+\infty\)
   6	2	1	\(\min\{1+v[3]\}=\min\{2\}=2\)
   7	1	2	\(\min\{1+v[4],\,1+v[0]\}=\min\{+\infty,1\}=1\)
   8	\(+\infty\)	0	\(\min\{1+v[5],\,1+v[1]\}=\min\{+\infty,+\infty\}=+\infty\)
   9	3	1	\(\min\{1+v[6],\,1+v[2]\}=\min\{3,+\infty\}=3\)
   10	2	1	\(\min\{1+v[7],\,1+v[3]\}=\min\{2,2\}=2\)
   11	\(+\infty\)	0	\(\min\{1+v[8],\,1+v[4]\}=\min\{+\infty,+\infty\}=+\infty\)
   12	4	1	\(\min\{1+v[9],\,1+v[5]\}=\min\{4,+\infty\}=4\)

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

   \[ \begin{array}{l|rrrrrrrrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline {v[k]} & 0 & {+\infty} & {+\infty} & 1 & {+\infty} & {+\infty} & 2 & 1 & {+\infty} & 3 & 2 & {+\infty} & 4 \\ \hline \end{array} \]

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

   \[ \begin{array}{l|rrrrrrrrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline {s[k]} & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 2 & 0 & 1 & 1 & 0 & 1 \\ \hline \end{array} \]

2. Abbiamo il seguente array \(s\):

   \[ \begin{array}{l|rrrrrrrrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline {s[k]} & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 2 & 0 & 1 & 1 & 0 & 1 \\ \hline \end{array} \]

   Possiamo ricostruire una soluzione ottima partendo da \(k=12\) come segue:

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

   Quindi il vettore

   \[ (4,0) \]

   è una soluzione ottima: il suo valore totale è \(4\cdot3=12=c\). Il valore ottimo è

   \[ v[12]=4. \]

Esercizio 27.5: Esercizio 5: problema del cambio monete

Consideriamo la seguente istanza del CCP, in cui il resto da restituire è \(c=9\) e i tagli sono

\[ w=(2,3,7). \]

Domande

1. Mostrare l'esecuzione dell'algoritmo di PD bottom-up riportando, per ogni iterazione, i valori dell'array \(v\) e dell'array \(s\).

2. Usando l'array \(s\), ricostruire una soluzione ottima in notazione intera \((x_1,x_2,x_3)\) e riportare il valore ottimo.

Soluzione

1. Esecuzione passo per passo dell'algoritmo di PD bottom-up

   Per ogni passo dell'algoritmo di PD, la tabella riporta il resto \(k\), le celle \(v[k]\) e \(s[k]\) e l'operazione eseguita; \(s[k]\) è l'indice \(j\) del taglio della moneta usata. In caso di pareggio si tiene l'indice minimo, perché \(m\) viene aggiornato solo quando il valore è strettamente minore. Il valore \(+\infty\) indica un resto che non si può restituire, per il quale \(s[k]=0\).

   \(k\)	\(v[k]\)	\(s[k]\)	Azione
   0	0	0	\(v[0]\leftarrow 0\), \(s[0]\leftarrow 0\)
   1	\(+\infty\)	0	nessun taglio \(w_j\le 1\): \(v[1]\leftarrow +\infty\)
   2	1	1	\(\min\{1+v[0]\}=\min\{1\}=1\)
   3	1	2	\(\min\{1+v[1],\,1+v[0]\}=\min\{+\infty,1\}=1\)
   4	2	1	\(\min\{1+v[2],\,1+v[1]\}=\min\{2,+\infty\}=2\)
   5	2	1	\(\min\{1+v[3],\,1+v[2]\}=\min\{2,2\}=2\)
   6	2	2	\(\min\{1+v[4],\,1+v[3]\}=\min\{3,2\}=2\)
   7	1	3	\(\min\{1+v[5],\,1+v[4],\,1+v[0]\}=\min\{3,3,1\}=1\)
   8	3	1	\(\min\{1+v[6],\,1+v[5],\,1+v[1]\}=\min\{3,3,+\infty\}=3\)
   9	2	1	\(\min\{1+v[7],\,1+v[6],\,1+v[2]\}=\min\{2,3,2\}=2\)

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

   \[ \begin{array}{l|rrrrrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline {v[k]} & 0 & {+\infty} & 1 & 1 & 2 & 2 & 2 & 1 & 3 & 2 \\ \hline \end{array} \]

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

   \[ \begin{array}{l|rrrrrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline {s[k]} & 0 & 0 & 1 & 2 & 1 & 1 & 2 & 3 & 1 & 1 \\ \hline \end{array} \]

2. Abbiamo il seguente array \(s\):

   \[ \begin{array}{l|rrrrrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline {s[k]} & 0 & 0 & 1 & 2 & 1 & 1 & 2 & 3 & 1 & 1 \\ \hline \end{array} \]

   Possiamo ricostruire una soluzione ottima partendo da \(k=9\) come segue:

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

   Quindi il vettore

   \[ (1,0,1) \]

   è una soluzione ottima: il suo valore totale è \(1\cdot2+1\cdot7=9=c\). Il valore ottimo è

   \[ v[9]=2. \]