La programmazione dinamica (PD) risolve un problema combinando i valori ottimi di sottoproblemi memorizzati in una tabella. Quali due proprietà deve avere il problema perché la PD sia corretta e utile?
Sottostruttura ottima e sottoproblemi sovrapposti
Sottostruttura ottima e sottoproblemi indipendenti
Funzione obiettivo lineare e vincoli interi
Matrice totalmente unimodulare e dati interi
Spiegazione. La sottostruttura ottima rende corretta la ricorrenza; i sottoproblemi sovrapposti rendono utile la tabella (lookup table) che memorizza i valori già calcolati.
In programmazione dinamica (PD), che cosa succede se un problema ha la sottostruttura ottima ma ogni sottoproblema compare una sola volta nella ricorsione?
La tabella rende l'algoritmo polinomiale nella dimensione dell'input
La ricorrenza diventa sbagliata e va corretta con più casi base
La tabella va riempita dall'alto verso il basso, non dal basso
La tabella non dà vantaggi: l'algoritmo è una semplice ricorsione
Spiegazione. Senza sottoproblemi sovrapposti non c'è nulla da riutilizzare. Senza sottostruttura ottima, invece, sarebbe la ricorrenza a essere sbagliata.
Un algoritmo di programmazione dinamica (PD) riempie una tabella con i valori ottimi dei sottoproblemi. Come si ottiene una soluzione ottima, oltre al valore ottimo?
Leggendo la sola tabella dei valori in avanti, dallo stato iniziale a quello finale
Rieseguendo la ricorsione dall'alto verso il basso, senza alcuna memorizzazione
Memorizzando le decisioni in un'altra tabella e leggendole a ritroso dallo stato finale
Memorizzando le decisioni in un'altra tabella e leggendole in avanti dallo stato iniziale
Spiegazione. Il progetto ha due passi: il valore ottimo (ricorrenza, casi base, tabella bottom-up) e una soluzione ottima (decisioni memorizzate e lette all'indietro).
Un algoritmo di programmazione dinamica (PD) segue il paradigma «dividi, conquista e combina». Che cosa dice il principio di combinazione?
Si sceglie il sottoproblema migliore e si scartano gli altri
Si costruisce una soluzione ottima del problema dalle soluzioni ottime dei sottoproblemi
Si scompone il problema in sottoproblemi più piccoli dello stesso tipo
Si risolvono i sottoproblemi piccoli direttamente, senza ricorsione
Spiegazione. Dividere genera i sottoproblemi, conquistare li risolve (ricorsivamente, o direttamente se piccoli), combinare unisce le loro soluzioni ottime in una soluzione ottima del problema.
Per il problema dello zaino con $n$ oggetti la forza bruta elenca i $2^n$ sottoinsiemi. In che cosa la programmazione dinamica (PD) evita questa enumerazione?
Memorizza il valore ottimo di ogni sottoproblema in una tabella e lo riusa quando il sottoproblema ricompare
Scarta a priori i sottoinsiemi con profitto basso, come un'euristica greedy
Risolve il rilassamento lineare e arrotonda la soluzione
Esamina i sottoinsiemi in ordine casuale e si ferma al primo ammissibile
Spiegazione. I sottoproblemi distinti sono molti meno delle soluzioni (per il KP $(n+1)(c+1)$ contro $2^n$): ciascuno si risolve una volta e il suo valore si legge dalla tabella (lookup table).
Nella programmazione dinamica (PD) i sottoproblemi generati dalla scomposizione sono «indipendenti». Che cosa significa?
Ciascuno compare una sola volta nella ricorsione
Hanno tutti la stessa dimensione
Le loro soluzioni ottime non hanno elementi in comune
Ciascuno si può risolvere senza informazioni sulla soluzione degli altri
Spiegazione. Indipendenti vuol dire che un sottoproblema si risolve da solo; può però comparire più volte nella ricorsione (sottoproblemi sovrapposti), ed è proprio questo che rende utile la tabella.
In programmazione dinamica (PD), che cosa afferma la proprietà di sottostruttura ottima di una scomposizione ricorsiva?
Ogni soluzione ottima di un sottoproblema è ottima anche per il problema
I sottoproblemi si ripetono molte volte nella ricorsione
Una soluzione ottima del problema si ottiene combinando soluzioni ottime dei suoi sottoproblemi
Ogni sottoproblema ha una soluzione ottima unica
Spiegazione. La sottostruttura ottima garantisce la correttezza della ricorrenza; la ripetizione dei sottoproblemi è l'altra proprietà, quella dei sottoproblemi sovrapposti, che rende la PD efficiente.
Quale è il primo passo nel progetto di un algoritmo di programmazione dinamica (PD)?
Calcolare un upper bound con un'euristica
Individuare la scomposizione ricorsiva in sottoproblemi e verificare sottostruttura ottima e sottoproblemi sovrapposti
Scrivere il modello di programmazione lineare intera e il suo rilassamento
Ordinare i dati per efficienza non crescente
Spiegazione. Prima si definisce la scomposizione e si controllano le due proprietà; poi si calcola il valore ottimo con la ricorrenza e i casi base, e infine si ricostruisce una soluzione ottima.
In programmazione dinamica (PD) il valore ottimo si può calcolare dall'alto verso il basso (top-down, ricorsione con tabella) o dal basso verso l'alto (bottom-up). Che cosa richiede l'approccio bottom-up?
Un ordine dei sottoproblemi in cui ognuno viene dopo quelli da cui dipende
Che i sottoproblemi non si ripetano mai
Che la tabella sia riempita in ordine casuale
Che la ricorrenza abbia un solo caso base
Spiegazione. Bottom-up riempie la tabella partendo dai casi base, in un ordine (per esempio capacità crescenti) che rende già disponibili le celle lette dalla ricorrenza. Top-down segue invece la ricorsione e memorizza i valori calcolati.
Fra gli algoritmi di programmazione dinamica del modulo, quale ha un numero di passi polinomiale nella dimensione dell'input (e non solo pseudo-polinomiale)?
La PD per lo zaino 0-1, $\Theta(nc)$
La PD per lo zaino limitato, $\Theta(nc\,b_{\max})$
La PD per il lot sizing con capacità, $O(mDC)$
Wagner e Whitin per il lot sizing senza capacità, $\Theta(m^2)$ con $m$ periodi
Spiegazione. $m$ è il numero di periodi, e l'input contiene $m$ domande: $\Theta(m^2)$ è polinomiale. Gli altri tempi contengono numeri dell'input (capacità $c$, limite $b_{\max}$, domanda $D$), esponenziali nel numero di cifre.
Nella programmazione dinamica per lo zaino multidimensionale (MDKP) e per lo zaino multiplo (MKP), lo stato contiene un vettore di $m$ capacità residue. Quando il numero di passi è pseudo-polinomiale?
Mai, perché il vettore rende il problema fortemente polinomiale
Solo quando tutte le capacità sono uguali
Solo per un numero $m$ fissato di dimensioni o di zaini
Sempre, perché ogni capacità è un numero dell'input
Spiegazione. La tabella ha una dimensione per ogni capacità, quindi un numero di stati $\prod_d(c_d+1)$: con $m$ fisso è pseudo-polinomiale, con $m$ parte dell'input cresce esponenzialmente in $m$.
In un algoritmo di programmazione dinamica (PD), che cosa contiene la lookup table?
I sottoproblemi ancora da risolvere, in ordine di priorità
Il valore ottimo di ogni sottoproblema già risolto, letto quando il sottoproblema ricompare
L'elenco di tutte le soluzioni ammissibili del problema
Le soluzioni del rilassamento lineare di ogni sottoproblema
Spiegazione. La tabella evita di ricalcolare i sottoproblemi sovrapposti: ogni valore si calcola una volta. Per ricostruire una soluzione si memorizzano anche le decisioni, in un'altra tabella.
La programmazione dinamica richiede la sottostruttura ottima: una soluzione ottima si compone di soluzioni ottime dei sottoproblemi. Che cosa succede in un problema dove questa proprietà manca?
La PD diventa polinomiale
La tabella ha meno celle
Combinare i valori ottimi dei sottoproblemi può dare una soluzione non ottima, e la ricorrenza non è corretta
La PD resta corretta ma più lenta
Spiegazione. Senza sottostruttura ottima la soluzione ottima può usare per un sottoproblema una soluzione non ottima, che la tabella non memorizza.
Fra gli algoritmi di PD del modulo, quale coppia ha un numero di passi esponenziale nel numero di vincoli di capacità (zaini o dimensioni), e non solo pseudo-polinomiale?
Lot sizing senza capacità e zaino con setup
Zaino multidimensionale e zaini multipli, con uno stato per ogni vettore di capacità
Zaino 0/1 e subset sum
Taglio delle aste e cambio monete
Spiegazione. Lo stato è un vettore $\vet k$ con $\prod(c_d+1)$ valori: esponenziale nel numero di capacità. Gli altri algoritmi hanno una sola capacità o sono polinomiali.
Un algoritmo ricorsivo senza memoria e un algoritmo di programmazione dinamica usano la stessa ricorrenza. Perché la PD può richiedere tempo pseudo-polinomiale invece che esponenziale?
I sottoproblemi si ripetono, e la PD risolve ciascuno una volta sola memorizzandone il valore nella tabella
Perché la PD esamina meno soluzioni ammissibili per ogni sottoproblema
Perché la PD usa una ricorrenza diversa
Perché la PD non ha bisogno della sottostruttura ottima
Spiegazione. Il numero di sottoproblemi distinti (per esempio $(n+1)(c+1)$ per lo zaino) limita il lavoro; la ricorsione senza memoria li ricalcola ogni volta che compaiono.
Gli algoritmi di programmazione dinamica richiedono due proprietà del problema: sottostruttura ottima e sottoproblemi sovrapposti. Che cosa succede se i sottoproblemi non si sovrappongono (ognuno compare una sola volta)?
La PD diventa scorretta
La PD diventa polinomiale
La tabella ha più celle dei sottoproblemi
La PD resta corretta ma non risparmia nulla rispetto alla ricorsione: conviene un approccio «dividi e conquista»
Spiegazione. La memorizzazione serve solo se un sottoproblema viene richiesto più volte; senza sovrapposizione il costo è lo stesso della ricorsione.
Nel progetto di un algoritmo di programmazione dinamica, dopo aver definito i sottoproblemi e la formula ricorsiva con i casi base, in che ordine si riempie la tabella nell'approccio bottom-up?
Dal sottoproblema più grande al più piccolo
Solo lungo la diagonale
In un ordine in cui ogni sottoproblema viene dopo tutti quelli da cui dipende
In ordine casuale
Spiegazione. Nella PD dello zaino, per esempio, la riga $j$ usa solo la riga $j-1$: si riempiono le righe in ordine crescente. Poi si ricostruisce la soluzione risalendo la tabella.
Fra gli algoritmi di programmazione dinamica del modulo, quali hanno un numero di passi polinomiale nella dimensione dell'istanza, e non solo pseudo-polinomiale?
Tutti
Wagner-Whitin per il lot sizing senza capacità ($\Theta(m^2)$) e il taglio delle aste ($\Theta(n^2)$)
La PD dello zaino 0/1 e quella del subset sum
La PD dello zaino multidimensionale
Spiegazione. Nell'ULS il numero di passi dipende solo dal numero di periodi; nel taglio delle aste $n$ è anche il numero di prezzi in input. Le PD di zaino dipendono dal valore della capacità.
Un problema ha la sottostruttura ottima e i sottoproblemi sovrapposti. Che cosa garantisce un algoritmo di programmazione dinamica (PD) basato su una ricorrenza corretta?
Una soluzione ottima in tempo polinomiale nell'input
Una soluzione con rapporto di approssimazione garantito
Ogni sottoproblema risolto tante volte quante compare
Una soluzione ottima, con ogni sottoproblema risolto una volta sola
Spiegazione. La sottostruttura ottima rende esatta la ricorrenza; la tabella evita di ricalcolare i sottoproblemi. Il tempo può essere solo pseudo-polinomiale.
In programmazione dinamica (PD), quale proprietà del problema rende corretta la ricorrenza, cioè fa sì che dia il valore ottimo?
I dati interi e positivi
Un numero polinomiale di sottoproblemi
La sottostruttura ottima
I sottoproblemi sovrapposti
Spiegazione. Con la sottostruttura ottima una soluzione ottima si compone di soluzioni ottime dei sottoproblemi. I sottoproblemi sovrapposti rendono utile la tabella, non corretta la ricorrenza.
Un algoritmo di PD ha $S$ sottoproblemi distinti e calcola ciascuno confrontando al più $d$ valori già noti, ognuno in tempo costante. Quanti passi esegue per riempire la tabella?
$O(S+d)$
$O(S^{d})$
$O(d^{S})$
$O(S\,d)$
Spiegazione. Ogni sottoproblema si calcola una volta, con $O(d)$ passi: in tutto $O(S\,d)$.
In un algoritmo di PD il valore ottimo si calcola con la ricorrenza (passo 1). Come si ottiene una soluzione ottima (passo 2)?
Si memorizza la scelta fatta in ogni cella e si ripercorre all'indietro
Si risolve di nuovo il problema con un solver PLI
Si prende la cella di valore massimo di ogni riga
Si ordina la tabella per valori decrescenti
Spiegazione. Una tabella aggiuntiva registra quale termine della ricorrenza ha dato il valore: leggendola a ritroso dall'ultima cella si ricostruisce una soluzione.
Nella programmazione dinamica per il problema dello zaino (KP: pesi $w_j$, capacità $c$), con un solo vettore $v[0..c]$ aggiornato oggetto per oggetto, perché per ogni oggetto $j$ le capacità $k$ si scorrono da $c$ verso $0$?
Altrimenti $v[k-w_j]$ non sarebbe ancora calcolato, e la ricorrenza leggerebbe celle vuote
Così il numero di passi scende da $\Theta(nc)$ a $\Theta(c)$, perché si salta metà vettore
Così si riempie per prima la cella $v[c]$, che contiene il valore ottimo
Altrimenti $v[k-w_j]$ conterrebbe già l'oggetto $j$, che potrebbe essere scelto più volte
Spiegazione. Scorrendo in ordine crescente si leggerebbe un valore già aggiornato con l'oggetto $j$ e si risolverebbe lo zaino illimitato. Il numero di passi resta $\Theta(nc)$.
Nel problema dello zaino (KP, capacità $c$, $P=\sum_j p_j$), il secondo algoritmo di PD calcola $u(j,q)$, il peso minimo di un sottoinsieme di $\{1,\dots,j\}$ con profitto totale esattamente $q$. Dove si legge il valore ottimo?
$\max\{u(n,q): q\in\{0,\dots,P\}\}$
$u(n,c)$
$\max\{q\in\{0,\dots,P\}: u(n,q)\le c\}$
$\min\{q\in\{0,\dots,P\}: u(n,q)\ge c\}$
Spiegazione. $u(n,q)$ non è un profitto ma un peso minimo: il profitto $q$ è ottenibile se il peso minimo non supera la capacità. Questo algoritmo esegue $\Theta(nP)$ passi.
Nella PD per il problema dello zaino, $v(j,k)$ è il valore ottimo con gli oggetti $1,\dots,j$ e capacità $k$. Nella ricostruzione di una soluzione ottima, partendo da $(n,c)$, come si aggiornano gli indici quando l'oggetto $j$ è scelto?
$j$ diminuisce di $1$ e $k$ diminuisce di $p_j$
$j$ diminuisce di $1$ e $k$ diminuisce di $w_j$
$j$ diminuisce di $1$ e $k$ resta uguale
$j$ resta uguale e $k$ diminuisce di $w_j$
Spiegazione. A ogni passo l'indice dell'oggetto scende di uno; la capacità scende di $w_j$ solo se l'oggetto $j$ è scelto (cioè se $v(j,k)\ne v(j-1,k)$).
Nella prima PD per lo zaino 0-1 (KP), $v(j,k)$ è il massimo profitto con gli oggetti $1,\dots,j$ e capacità $k$, per $j=0,\dots,n$ e $k=0,\dots,c$. Quante celle ha la tabella con $n=4$ oggetti e capacità $c=9$?
$40$
$16$
$50$
$36$
Spiegazione. $(n+1)(c+1)=5\cdot 10=50$: le righe partono da $j=0$ e le colonne da $k=0$. $16=2^4$ conta i sottoinsiemi degli oggetti.
Nella PD a liste per lo zaino 0-1, uno stato è una coppia (peso, profitto) di un sottoinsieme, e $L_j$ tiene gli stati non dominati con gli oggetti $1,\dots,j$; $(w,p)$ domina $(w',p')$ se $w\le w'$ e $p\ge p'$. Con oggetti $(w_1,p_1)=(2,6)$, $(w_2,p_2)=(3,5)$ e $L_0=\{(0,0)\}$, quanti stati ha $L_2$?
$5$
$3$
$4$
$2$
Spiegazione. I sottoinsiemi danno $(0,0)$, $(2,6)$, $(3,5)$, $(5,11)$; $(3,5)$ è dominato da $(2,6)$, che pesa meno e vale di più. Restano $3$ stati.
Nella PD a liste per lo zaino 0-1 (capacità intera $c$), la lista $L_j$ contiene solo stati (peso, profitto) non dominati e di peso al più $c$. Perché ha al più $c+1$ stati?
Gli stati non dominati hanno pesi tutti diversi, e i pesi interi possibili sono $0,1,\dots,c$
Ogni oggetto aggiunge al più uno stato alla lista
Gli stati non dominati hanno profitti tutti uguali
La lista si svuota quando supera $c$ elementi
Spiegazione. Due stati con lo stesso peso sono confrontabili, e uno domina l'altro; quindi in $L_j$ i pesi sono distinti e, ordinati per peso crescente, anche i profitti sono crescenti. Il numero di stati è quindi al più $\min\{2^j,c+1\}$.
Nella PD a liste per lo zaino 0-1, perché si può scartare uno stato $(w',p')$ dominato da $(w,p)$, cioè con $w\le w'$ e $p\ge p'$?
Perché $(w',p')$ non è ammissibile
Perché gli stati dominati hanno sempre peso maggiore della capacità
Perché la lista deve avere al più $n$ elementi
Ogni insieme di oggetti residui aggiungibile a $(w',p')$ si aggiunge anche a $(w,p)$, con profitto non minore
Spiegazione. Se $S'$ entra con $(w',p')$, entra anche con $(w,p)$ perché $w\le w'$, e dà profitto $p+p(S')\ge p'+p(S')$: nessuna soluzione ottima va persa.
Nella seconda PD per lo zaino 0-1, $u(j,q)$ è il peso minimo di un sottoinsieme degli oggetti $1,\dots,j$ con profitto esattamente $q$, per $q=0,\dots,P$ con $P=\sum_j p_j$. Quante celle ha la tabella con profitti $p=(6,5,8,9)$?
$50$
$140$
$145$
$116$
Spiegazione. $P=28$, quindi $(n+1)(P+1)=5\cdot 29=145$. Il numero di passi è $\Theta(nP)$: conviene quando i profitti sono piccoli rispetto alla capacità.
Nella seconda PD per lo zaino 0-1, $u(j,q)$ è il peso minimo di un sottoinsieme degli oggetti $1,\dots,j$ con profitto esattamente $q$ ($+\infty$ se non esiste). Oggetti: $p=(3,2,4)$, $w=(4,3,5)$. Quanto vale $u(3,5)$?
$8$
$7$
$+\infty$
$5$
Spiegazione. L'unico sottoinsieme di profitto $5$ è $\{1,2\}$, di peso $4+3=7$. $\{1,3\}$ ha profitto $7$, non $5$; $5$ confonde peso e profitto.
Nella seconda PD per lo zaino 0-1, $u(n,q)$ è il peso minimo per ottenere profitto esattamente $q$. Con capacità $c=8$ l'ultima riga, per $q=0,\dots,8$, è $(0,+\infty,3,4,+\infty,7,6,9,10)$. Quanto vale il valore ottimo dello zaino?
$6$
$8$
$5$
$7$
Spiegazione. Il valore ottimo è il più grande $q$ con $u(n,q)\le c$: $u(n,8)=10$ e $u(n,7)=9$ superano $8$, $u(n,6)=6\le 8$. Quindi $6$.
Nell'implementazione a liste della seconda PD per lo zaino 0-1 (stati (peso, profitto), liste $L_j$ di stati non dominati), in quale momento si usa la capacità $c$?
A ogni passo: gli stati di peso maggiore di $c$ si scartano subito
All'inizio: si scartano gli oggetti di peso maggiore di $c/2$
Mai: il valore ottimo è il profitto massimo in $L_n$
Solo alla fine: fra gli stati di $L_n$ si prendono quelli di peso al più $c$
Spiegazione. Come nella ricorrenza su $u(j,q)$, la capacità non compare nelle liste: $L_j$ raccoglie gli stati di tutti i sottoinsiemi, anche troppo pesanti, e il controllo $w\le c$ si fa su $L_n$.
Nella PD a liste per lo zaino 0-1, l'ultima lista di stati (peso, profitto) non dominati è $L_n=\{(0,0),(2,6),(5,11),(8,14),(9,15),(11,19)\}$ e la capacità è $c=9$. Quanto vale il valore ottimo?
$14$
$11$
$15$
$19$
Spiegazione. Fra gli stati di peso al più $9$ il profitto massimo è $15$, dello stato $(9,15)$. $(11,19)$ supera la capacità.
Zaino 0/1 con capacità $c=5$ e $3$ oggetti, $p=(6,7,8)$ e $w=(2,3,3)$. Degli $8$ sottoinsiemi di oggetti, quanti sono soluzioni ammissibili (peso totale al più $c$)?
$4$
$5$
$6$
$8$
Spiegazione. Sono inammissibili solo $\{2,3\}$ (peso $6$) e $\{1,2,3\}$ (peso $8$); l'insieme vuoto e i tre singoletti, $\{1,2\}$ e $\{1,3\}$ (peso $5$) sono ammissibili.
Una soluzione dello zaino 0/1 con $n$ oggetti si codifica con il vettore binario $(x_1,\dots,x_n)$. Con $p=(6,7,8)$, $w=(2,3,3)$ e $c=5$, che cosa rappresenta $(1,0,1)$?
La soluzione $\{1,3\}$, di peso $5\le c$ e profitto $14$
La soluzione $\{2\}$, di peso $3$ e profitto $7$
Una soluzione inammissibile di peso $8$
Due copie dell'oggetto $1$ e una dell'oggetto $3$
Spiegazione. $x_j=1$ se e solo se l'oggetto $j$ è selezionato: peso $2+3=5$, profitto $6+8=14$. Le copie multiple appartengono allo zaino illimitato.
L'algoritmo di PD per lo zaino 0/1 esegue $\Theta(nc)$ passi ($n$ oggetti, capacità $c$). Si moltiplicano per $1000$ la capacità e tutti i pesi di un'istanza. Che cosa succede al numero di passi e alla dimensione dell'istanza (in bit)?
Entrambi crescono di $1000$ volte
I passi non cambiano, perché la soluzione ottima è la stessa
I passi crescono di circa $10$ volte
I passi crescono di circa $1000$ volte, la dimensione solo di circa $10$ bit per numero
Spiegazione. $\Theta(nc)$ dipende dal valore di $c$, mentre scrivere $1000c$ richiede solo $\log_2 1000\approx10$ bit in più: per questo l'algoritmo è pseudo-polinomiale e non polinomiale.
La PD per lo zaino 0/1 ha una versione con la matrice $v(j,k)$, $(n+1)(c+1)$ celle, e una versione con un solo vettore di $c+1$ celle. Come si confrontano numero di passi e memoria?
Il vettore richiede $\Theta(nc^2)$ passi
Identici anche in memoria
Stesso numero di passi $\Theta(nc)$; il vettore usa memoria $\Theta(c)$ invece di $\Theta(nc)$
Il vettore è più veloce, $\Theta(c)$ passi
Spiegazione. Entrambe eseguono gli stessi due cicli annidati; il vettore riusa la stessa riga per ogni oggetto (scorrendo le capacità da $c$ a $w_j$), ma non conserva la tabella per ricostruire la soluzione.
Nella PD con liste per lo zaino 0/1, la lista $L_j$ contiene gli stati non dominati costruiti con gli oggetti $1,\dots,j$, con pesi distinti in $\{0,\dots,c\}$. Con $c=100$, quanti stati può contenere al massimo $L_3$?
$300$
$8$, perché $|L_j|\le\min\{2^j,c+1\}$
$101$
$3$
Spiegazione. Con tre oggetti ci sono $2^3=8$ sottoinsiemi, quindi al più $8$ stati, molto meno delle $101$ capacità della matrice.
Il secondo algoritmo di PD per lo zaino 0/1 calcola, per ogni profitto obiettivo $q\in\{0,\dots,P\}$ con $P=\sum_jp_j$, il peso minimo per ottenerlo, in $\Theta(nP)$ passi. Quando conviene rispetto al primo algoritmo, $\Theta(nc)$?
Quando i profitti sono piccoli e la capacità è grande ($P\ll c$)
Quando la capacità è piccola e i profitti grandi
Sempre, perché $\Theta(nP)$ è polinomiale
Mai: i due algoritmi hanno sempre lo stesso numero di passi
Spiegazione. I due algoritmi sono pseudo-polinomiali in numeri diversi; il secondo è alla base dell'FPTAS, che arrotonda i profitti per rendere $P$ piccolo.
Nella seconda PD per lo zaino 0/1, la matrice $u(j,q)$ (peso minimo per ottenere il profitto $q$ con gli oggetti $1,\dots,j$) ha $(n+1)(P+1)$ celle, con $P=\sum_jp_j$. Perché l'implementazione con liste può essere molto più piccola?
Perché le liste ignorano gli oggetti di peso grande
Perché le liste memorizzano solo l'ultima riga
Non lo è: hanno sempre $(n+1)(P+1)$ elementi
La maggior parte delle celle vale $+\infty$ (profitti non raggiungibili); le liste conservano solo gli stati raggiungibili
Spiegazione. Con gli oggetti $1,\dots,j$ si ottengono al più $2^j$ profitti diversi, quindi $|L_j|\le\min\{2^j,P+1\}$; le celle $+\infty$ non entrano nelle liste.
Zaino 0/1 con $n$ oggetti: quanti sottoinsiemi di oggetti ci sono, e quanti di essi la PD considera esplicitamente?
$n!$ sottoinsiemi; la PD ne considera $n^2$
$n^2$ sottoinsiemi; la PD li considera tutti
$2^n$ sottoinsiemi; la PD non li enumera, ma calcola $(n+1)(c+1)$ valori $v(j,k)$
$2^n$ sottoinsiemi; la PD li considera tutti
Spiegazione. Ogni oggetto si sceglie in modo indipendente, da cui $2^n$. La PD raggruppa i sottoinsiemi per (ultimo oggetto considerato, capacità usata) e tiene solo il migliore.
Contando le righe dello pseudocodice, la prima PD per lo zaino 0/1 esegue nel caso peggiore $S(n,c)=4nc+4n+2c+4$ passi. Quanti sono per $n=3$ e $c=5$, e qual è l'ordine di crescita?
$86$; $\Theta(n+c)$
$60$; $\Theta(nc)$
$96$; $\Theta(n^2c)$
$86$; $\Theta(nc)$
Spiegazione. $4\cdot15+12+10+4=86$. Il termine dominante è $4nc$, quindi $S(n,c)=\Theta(nc)$: il limite di $S/(nc)$ è $4$.
Nella PD con liste per lo zaino 0/1, per ogni oggetto si costruisce $M_j$ da $L_{j-1}$ e si fondono le due liste con Merge. Perché i passi restano $\Theta(nc)$ nel caso peggiore?
Perché Merge ordina le liste in $\Theta(c\log c)$
Perché le liste ignorano la capacità
Ogni lista ha al più $c+1$ stati (pesi distinti in $\{0,\dots,c\}$), e Merge li scandisce una volta per oggetto
Perché le liste hanno sempre un solo stato
Spiegazione. $|L_{j-1}|+|M_j|\le2(c+1)$ stati per oggetto, con lavoro costante per stato; nel caso medio le liste sono molto più corte della matrice.
Sull'istanza dello zaino 0/1 con $c=5$, $p=(6,7,8)$, $w=(2,3,3)$ le liste della PD contengono $1$, $2$, $4$ e $4$ stati. Quante celle ha invece la matrice $v(j,k)$?
$8$
$24$, cioè $(n+1)(c+1)$
$11$
$15$
Spiegazione. $(3+1)(5+1)=24$ celle, contro $11$ stati in tutto nelle liste: le liste memorizzano solo gli stati raggiungibili e non dominati.
La seconda PD per lo zaino 0/1 esegue $S(n,P)=4nP+7n+4P+8$ passi, con $P=\sum_jp_j$. Con $n=3$ e profitti $p=(6,7,8)$, quanto vale $S$?
$365$
$252$
$86$
$345$
Spiegazione. $P=21$: $4\cdot3\cdot21+7\cdot3+4\cdot21+8=252+21+84+8=365$. $252$ è solo il termine dominante; $86$ è il numero di passi della prima PD con $c=5$.
La seconda PD per lo zaino 0/1 ha una versione con matrice $u(j,q)$ e una con un solo vettore indicizzato dal profitto obiettivo $q\in\{0,\dots,P\}$. Quanta memoria usa la versione con vettore?
$\Theta(nP)$, come la matrice
$\Theta(c)$
$\Theta(n)$
$\Theta(P)$, con lo stesso numero di passi $\Theta(nP)$
Spiegazione. Il vettore ha $P+1$ celle e si aggiorna oggetto per oggetto; come per la prima PD, rinunciare alla matrice complica la ricostruzione della soluzione.
Nella seconda PD con liste per lo zaino 0/1 gli stati hanno profitti distinti in $\{0,\dots,P\}$, con $P=\sum_jp_j$. Con $P=21$, quanti stati può contenere al più la lista $L_2$, costruita con i primi due oggetti?
$2$
$21$
$4$, perché $|L_j|\le\min\{2^j,P+1\}$
$22$
Spiegazione. Due oggetti danno $2^2=4$ sottoinsiemi, quindi al più $4$ profitti diversi, molti meno delle $P+1=22$ colonne della matrice.
La matrice $u(j,q)$ della seconda PD per lo zaino 0/1 (peso minimo per ottenere esattamente il profitto $q$ con gli oggetti $1,\dots,j$) ha $(n+1)(P+1)$ celle. Quante sono con $n=3$ e $p=(6,7,8)$?
$84$
$88$
$63$
$24$
Spiegazione. $P=21$, quindi $4\cdot22=88$; la maggior parte vale $+\infty$, perché pochi profitti sono raggiungibili. $24$ sono le celle della prima PD con $c=5$.
Nella prima PD con liste per lo zaino 0/1 vale $|M_j|\le|L_{j-1}|$, nella seconda (stati indicizzati dal profitto) $|M_j|=|L_{j-1}|$. Da che cosa dipende la differenza?
Nella prima, aggiungere l'oggetto $j$ a uno stato può superare la capacità e lo stato si scarta; nella seconda ogni stato si estende con l'oggetto $j$
La seconda PD ignora i pesi
Nella seconda le liste sono ordinate per peso
Non c'è differenza: in entrambe vale l'uguaglianza
Spiegazione. Nella seconda PD si confronta il peso minimo con $c$ solo alla fine, per scegliere il profitto massimo raggiungibile.
Nello zaino illimitato (UKP: $n$ tipi di oggetto, profitto $p_j$, peso $w_j$, copie illimitate), la PD con tabella $v(j,k)$ (tipi $1,\dots,j$, capacità $k$) usa una ricorrenza con due termini. Quale termine permette di usare più copie del tipo $j$?
$p_j+v(j-1,k)$, che non riduce la capacità
$v(j-1,k)$, che esclude il tipo $j$
$p_j+v(j,k-w_j)$, che resta nella riga $j$
$p_j+v(j-1,k-w_j)$, che passa alla riga $j-1$
Spiegazione. Restare nella riga $j$ dopo aver inserito una copia permette di inserirne altre; con la riga $j-1$ si otterrebbe il KP 0/1.
Nello zaino illimitato (UKP), $v(k)$ è il massimo profitto con capacità $k$ e copie illimitate di ogni tipo. Quanto vale $v(k)$ se nessun tipo di oggetto entra nella capacità $k\ge 1$?
$v(k-1)$: si usa la capacità precedente
$0$: parte della capacità può restare inutilizzata
$-\infty$: la capacità va riempita esattamente
$+\infty$: il sottoproblema non è ammissibile
Spiegazione. Non serve riempire la capacità: se nessun tipo entra, la soluzione vuota è ammissibile e vale $0$. Il valore $+\infty$ serve nel cambio monete, dove il resto va dato esattamente.
Nello zaino illimitato (UKP: $n$ tipi di oggetto, capacità $c$), il primo algoritmo di PD riempie un vettore $v$ indicizzato dalla capacità residua. Quante celle ha e quanti passi esegue?
$c+1$ celle, $\Theta(nc)$ passi
$c$ celle, $\Theta(c)$ passi
$(n+1)(c+1)$ celle, $\Theta(nc)$ passi
$c+1$ celle, $\Theta(n^2c)$ passi
Spiegazione. Il valore ottimo dipende solo dalla capacità residua, quindi basta un vettore di $c+1$ celle (da $0$ a $c$); per ogni cella si provano gli $n$ tipi: $\Theta(nc)$, pseudo-polinomiale.
Nello zaino illimitato (UKP) il tipo $j$ si può usare al più $\lfloor c/w_j\rfloor$ volte. Con pesi $w=(2,3,4)$ e capacità $c=8$, quanti vettori $(x_1,x_2,x_3)$ con $0\le x_j\le\lfloor c/w_j\rfloor$ ci sono, prima di controllare la capacità?
$27$
$8$
$60$
$45$
Spiegazione. $\lfloor 8/2\rfloor+1=5$, $\lfloor 8/3\rfloor+1=3$, $\lfloor 8/4\rfloor+1=3$: $5\cdot3\cdot3=45$ vettori candidati, di cui solo alcuni rispettano la capacità.
Zaino illimitato (UKP) con due tipi, $p=(3,5)$ e $w=(2,3)$, capacità $c=7$. Con $v(0)=0$ e $v(k)=\max_{j:\,w_j\le k}\{p_j+v(k-w_j)\}$ ($0$ se nessun tipo entra), quanto vale $v(7)$?
$8$
$12$
$11$
$10$
Spiegazione. $v=(0,0,3,5,6,8,10,11)$ per $k=0,\dots,7$: per esempio due copie del tipo $1$ e una del tipo $2$. Il greedy per efficienza (due copie del tipo $2$) dà $10$, lo zaino 0-1 dà $8$.
Nella prima PD per lo zaino illimitato (UKP), $v(k)$ è il massimo profitto con capacità $k$ e $s(k)$ il tipo che realizza il massimo nella ricorrenza. Come si ricostruisce una soluzione ottima partendo da $k=c$?
Si legge $s(c)$: tutte le copie sono di quel tipo
Si prende una copia del tipo $s(k)$ e si pone $k\leftarrow k-w_{s(k)}$, finché nessun tipo entra
Si prende il tipo $s(k)$ e si passa al tipo successivo, come nel KP
Si prendono $\lfloor k/w_{s(k)}\rfloor$ copie di $s(k)$ e ci si ferma
Spiegazione. Ogni passo della ricorrenza aggiunge una copia di un tipo e riduce la capacità del suo peso; il tipo può ripetersi nei passi successivi.
Nella seconda PD per lo zaino illimitato (UKP), $v(j,k)=\max\{v(j-1,k),\ p_j+v(j,k-w_j)\}$ (il secondo termine se $w_j\le k$). In quale ordine si calcolano le celle con l'approccio bottom-up?
Riga per riga ($j$ crescente) e, in ogni riga, per $k$ crescente
Riga per riga e, in ogni riga, per $k$ decrescente
Colonna per colonna, per $j$ decrescente
In qualsiasi ordine, perché le celle sono indipendenti
Spiegazione. $v(j,k)$ legge $v(j-1,k)$ (riga precedente) e $v(j,k-w_j)$ (stessa riga, capacità minore): quest'ultima deve essere già calcolata, quindi $k$ cresce. È questo che permette più copie del tipo $j$.
Zaino illimitato (UKP) con tipi $p=(3,5)$, $w=(2,3)$. Nella seconda PD, $v(j,k)$ è il massimo profitto con i soli tipi $1,\dots,j$ e capacità $k$. Quanto vale $v(1,7)$?
$11$
$3$
$10$
$9$
Spiegazione. Con il solo tipo $1$ entrano $\lfloor 7/2\rfloor=3$ copie: $v(1,7)=9$. $11=v(2,7)$ usa anche il tipo $2$; $3$ è il valore di una sola copia.
Per lo zaino illimitato (UKP) con $n$ tipi e capacità $c$, la prima PD usa un vettore $v(k)$ e la seconda una tabella $v(j,k)$. Quale confronto è corretto?
La prima esegue $\Theta(nc)$ passi, la seconda $\Theta(n^2c)$
Hanno lo stesso numero di celle, ma la seconda è esponenziale
La prima ha $c+1$ celle, la seconda $(n+1)(c+1)$; entrambe eseguono $\Theta(nc)$ passi
La prima esegue $\Theta(c)$ passi, la seconda $\Theta(nc)$
Spiegazione. La prima calcola ogni $v(k)$ con un massimo su $n$ tipi; la seconda calcola ogni cella con due termini. Il lavoro totale è $\Theta(nc)$ in entrambi i casi.
Nella seconda PD per lo zaino illimitato (UKP), $v(j,k)$ usa i tipi $1,\dots,j$ e capacità $k$. Perché il caso base è $v(0,k)=0$ per ogni $k$, e non $-\infty$ per $k>0$?
Perché $-\infty$ non si può memorizzare in una tabella
Lo zaino non deve essere riempito: senza tipi disponibili la soluzione vuota è ammissibile e vale $0$
Perché i profitti sono positivi, quindi nessun valore è negativo
Perché la capacità $k$ è sempre nulla quando $j=0$
Spiegazione. Nell'UKP basta non superare la capacità. Nel taglio delle aste, dove l'asta va divisa per intero, la stessa ricorrenza usa invece $v(0,\ell)=-\infty$ per $\ell>0$.
Nella prima PD per lo zaino illimitato (UKP), per calcolare $v(k)=\max_{j:\,w_j\le k}\{p_j+v(k-w_j)\}$, quali celle già calcolate si leggono?
Le celle $v(k-w_j)$, una per ogni tipo $j$ con $w_j\le k$
Solo la cella $v(k-1)$
Tutte le celle $v(0),\dots,v(k-1)$
Le celle $v(k-w_j)$ della riga precedente, una per tipo
Spiegazione. Ogni termine corrisponde a una prima copia del tipo $j$ e legge il valore della capacità residua $k-w_j$; i termini sono al più $n$, da cui $\Theta(nc)$ passi.
Nello zaino illimitato (UKP) un tipo $i$ domina un tipo $j$ se $w_i\le w_j$ e $p_i\ge p_j$. Che cosa si può fare con il tipo $j$ dominato?
Niente: con copie illimitate nessun tipo è dominato
Usarlo solo per riempire la capacità residua
Eliminare invece il tipo $i$, che ha peso minore
Eliminarlo: ogni sua copia si sostituisce con una copia di $i$ senza superare la capacità né perdere profitto
Spiegazione. Sostituire una copia di $j$ con una di $i$ non aumenta il peso e non diminuisce il profitto, quindi esiste una soluzione ottima senza il tipo $j$.
Nello zaino illimitato (UKP) una soluzione è un vettore intero $(x_1,\dots,x_n)$, con $x_j$ copie del tipo $j$ e $\sum_jw_jx_j\le c$. Con $c=10$ e $w=(3,4)$, quale limite vale per ogni componente?
$x_1\le3$ e $x_2\le2$, cioè $x_j\le\lfloor c/w_j\rfloor$
$x_j\le1$
$x_1\le10$ e $x_2\le10$
$x_1+x_2\le1$
Spiegazione. Le copie di un solo tipo pesano già $w_jx_j\le c$: $\lfloor10/3\rfloor=3$, $\lfloor10/4\rfloor=2$. Le soluzioni sono quindi finite.
I due algoritmi di PD per lo zaino illimitato (UKP, copie illimitate di $n$ tipi, capacità $c$) eseguono entrambi $\Theta(nc)$ passi. Perché le copie illimitate non fanno crescere il numero di passi rispetto allo zaino 0/1?
Perché si considera al più una copia per tipo
Perché la capacità si riduce a $\lfloor c/n\rfloor$
Le copie fanno crescere i passi a $\Theta(nc^2)$
Ogni stato considera un tipo alla volta e riusa valori già calcolati con lo stesso tipo, senza enumerare il numero di copie
Spiegazione. Nella ricorrenza, dopo aver preso una copia del tipo $j$ si resta in uno stato che può prenderne un'altra: il numero di copie non è un ciclo esplicito, a differenza della PD del BKP ($\Theta(nc\,b_{\max})$).
Zaino illimitato con $c=10$ e due tipi di oggetto di pesi $w=(4,3)$. Le soluzioni candidate sono i vettori $(x_1,x_2)$ con $0\le x_j\le\lfloor c/w_j\rfloor$. Quante sono?
$121$
$12$
$6$
$4$
Spiegazione. $\lfloor10/4\rfloor=2$ e $\lfloor10/3\rfloor=3$: $(2+1)(3+1)=12$ candidate, di cui solo alcune rispettano la capacità.
Zaino illimitato con $c=10$, pesi $w=(3,4)$ e profitti $p=(5,7)$; una soluzione è il vettore $(x_1,x_2)$ dei numeri di copie. Quale vettore è ammissibile e quanto vale?
$(2,1)$, peso $10$, profitto $17$
$(3,1)$, peso $13$, profitto $22$
$(1,2)$, peso $11$, profitto $19$
$(0,3)$, peso $12$, profitto $21$
Spiegazione. $2\cdot3+1\cdot4=10\le c$ e $2\cdot5+7=17$; gli altri superano la capacità.
Nello zaino 0/1 la soluzione è un vettore binario, nello zaino illimitato un vettore di interi $x_j\in\Z_{\ge0}$. Perché nell'UKP due copie identiche non si contano come due soluzioni diverse?
Perché nell'UKP si prende al più una copia
Perché le copie hanno pesi diversi
Perché la capacità è illimitata
Il vettore registra solo quante copie di ogni tipo si prendono, non quale copia
Spiegazione. Le copie di un tipo sono indistinguibili: contare i sottoinsiemi di copie conterebbe più volte la stessa soluzione.
La prima PD per lo zaino illimitato calcola $v(k)$, il profitto massimo con capacità $k$, per $k=0,\dots,c$, provando per ogni $k$ gli $n$ tipi di oggetto. Con $c=10$ e $n=2$, quante valutazioni di tipo esegue circa, e di che ordine è il numero di passi?
Circa $2^{10}$; esponenziale
Circa $12$; $\Theta(n+c)$
Circa $20$; $\Theta(nc)$
Circa $100$; $\Theta(c^2)$
Spiegazione. Per ogni capacità $k=1,\dots,10$ si provano $2$ tipi: $20$ valutazioni, ciascuna in tempo costante. La versione InfoSol aggiunge un vettore di scelte con un numero costante di operazioni in più.
$v(k)=\max_j\{p_j+v(k-w_j)\}$ con al più una copia per tipo
$v(k)=v(k-1)+\max_jp_j$
Spiegazione. Si prende un'ultima copia di un tipo $j$ e si riusa il valore ottimo con capacità $k-w_j$, che può contenere altre copie dello stesso tipo; $v(k-1)$ copre il caso di capacità non usata.
La seconda PD per lo zaino illimitato usa una matrice sui tipi $1,\dots,j$ e sulle capacità, come la PD dello zaino 0/1, ma dopo aver preso il tipo $j$ resta nella riga $j$. Che cosa cambia rispetto alla PD dello zaino 0/1?
Il termine «prendo il tipo $j$» usa $v(j,k-w_j)$ invece di $v(j-1,k-w_j)$, così il tipo si può riprendere
Si usano le righe in ordine inverso
Il numero di passi diventa $\Theta(nc^2)$
Nulla: è la stessa ricorrenza
Spiegazione. Restare nella riga $j$ permette altre copie dello stesso tipo; il numero di passi resta $\Theta(nc)$ e la matrice InfoSol registra le scelte per la ricostruzione.
Nello zaino limitato (BKP) il tipo $j$ ha $b_j$ copie disponibili di peso $w_j$. Nella ricorrenza, per il tipo $j$ con $b_j=3$, $w_j=4$ e capacità residua $k=10$, quanti valori del numero di copie $d$ si provano?
$11$ ($d=0,\dots,10$)
$3$ ($d=0,1,2$)
$4$ ($d=0,1,2,3$)
$2$ ($d=1,2$)
Spiegazione. $d\in\{0,1,\dots,\min\{b_j,\lfloor k/w_j\rfloor\}\}=\{0,1,2\}$: contano sia il limite sulle copie sia la capacità.
Nello zaino limitato (BKP) il tipo $j$ ha $b_j$ copie disponibili, $b_{\max}=\max_j b_j$, e la capacità è $c$. Quale affermazione sul BKP e sulla sua PD è corretta?
Generalizza il KP ($b_j=1$) e l'UKP ($b_j=\lfloor c/w_j\rfloor$); la PD esegue $\Theta(nc\,b_{\max})$ passi
Generalizza il KP ($b_j=1$) ma non l'UKP; la PD esegue $\Theta(nc\,b_{\max})$ passi
Generalizza il KP ($b_j=1$) e l'UKP ($b_j=\lfloor c/w_j\rfloor$); la PD esegue $\Theta(nc)$ passi
È un caso particolare del KP; la PD è polinomiale perché $b_{\max}\le n$
Spiegazione. Con una copia per tipo si ha il KP, con $\lfloor c/w_j\rfloor$ copie l'UKP. Il ciclo più interno prova fino a $b_{\max}+1$ valori, quindi $\Theta(nc\,b_{\max})$, pseudo-polinomiale.
Nella PD dello zaino limitato (BKP), $s[j][k]$ è il numero di copie del tipo $j$ (peso $w_j$) scelte nello stato con tipi $1,\dots,j$ e capacità $k$. Nella ricostruzione, dopo aver letto $s[j][k]$, come si aggiornano gli indici?
$k\leftarrow k-s[j][k]$, e $j$ diminuisce di $1$
$k\leftarrow k-w_j$, e $j$ resta uguale
$k$ resta uguale, e $j$ diminuisce di $s[j][k]$
$k\leftarrow k-s[j][k]\,w_j$, e $j$ diminuisce di $1$
Spiegazione. Si tolgono le $s[j][k]$ copie scelte, ognuna di peso $w_j$; l'indice del tipo scende sempre di uno.
Nello zaino limitato (BKP) il tipo $j$ ha $b_j$ copie disponibili. Con $b=(2,2,1,1,1,1)$, quanti vettori $(x_1,\dots,x_6)$ con $0\le x_j\le b_j$ ci sono, prima di controllare la capacità?
$144$
$64$
$8$
$256$
Spiegazione. Ogni tipo ha $b_j+1$ scelte: $3\cdot3\cdot2^4=144$. $2^6=64$ sono le scelte con al più una copia per tipo.
Nello zaino limitato (BKP: profitti $p_j$, pesi $w_j$, copie disponibili $b_j$, capacità $c$), come si codifica una soluzione ammissibile?
Con un sottoinsieme degli oggetti di peso totale al più $c$
Con un vettore intero $x\ge 0$ tale che $\sum_j w_jx_j=c$
Con un vettore binario $x$ tale che $\sum_j b_jw_jx_j\le c$
Con un vettore intero $x$, $0\le x_j\le b_j$, tale che $\sum_j w_jx_j\le c$
Spiegazione. $x_j$ conta le copie del tipo $j$, limitate da $b_j$, e il peso totale non supera la capacità. Il sottoinsieme è la codifica del KP ($b_j=1$).
Zaino limitato (BKP) con due tipi: $p=(4,7)$, $w=(2,3)$, copie $b=(3,1)$, capacità $c=7$. Con $v(j,k)=\max_{0\le d\le\min\{b_j,\lfloor k/w_j\rfloor\}}\{d\,p_j+v(j-1,k-d\,w_j)\}$ e $v(0,k)=0$, quanto vale $v(2,7)$?
$11$
$16$
$15$
$12$
Spiegazione. $d=0$: $v(1,7)=3\cdot4=12$; $d=1$: $7+v(1,4)=7+8=15$. Il massimo è $15$. Con una copia per tipo (KP) si avrebbe $11$.
Nell'albero di ricorsione della PD per lo zaino limitato (BKP), ogni nodo è una chiamata $v(j,k)$ e i figli sono le chiamate generate dalla ricorrenza. Quanti figli ha al più il nodo $v(j,k)$?
$n$, uno per ogni tipo di oggetto
$\min\{b_j,\lfloor k/w_j\rfloor\}+1$, uno per ogni numero di copie del tipo $j$
$2$, come nel KP
$b_j$, uno per ogni copia disponibile
Spiegazione. Si provano $d=0,1,\dots,\min\{b_j,\lfloor k/w_j\rfloor\}$ copie, e ogni scelta genera la chiamata $v(j-1,k-d\,w_j)$. Con $b_j=1$ si ritrovano i due figli del KP.
Nella PD per lo zaino limitato (BKP), $v(j,k)$ è il massimo profitto con i tipi $1,\dots,j$ e capacità $k$. Quale proprietà ha ogni riga $v(j,\cdot)$?
È non decrescente in $k$: con più capacità le soluzioni ammissibili sono di più
È crescente in $k$ in senso stretto
È costante: il profitto non dipende dalla capacità
Decresce quando $k$ supera $\sum_j b_jw_j$
Spiegazione. Una soluzione ammissibile con capacità $k$ lo è anche con capacità $k+1$, perché lo zaino non va riempito; il valore può però restare uguale per più capacità consecutive.
Nella PD per lo zaino limitato (BKP), $v(j,k)$ è il massimo profitto con i tipi $1,\dots,j$ e capacità $k$. Quanto vale il caso base $v(0,k)$, per $k=0,\dots,c$?
$-\infty$ per $k\ge 1$
$k$ per ogni $k$
$+\infty$ per $k\ge 1$
$0$ per ogni $k$
Spiegazione. Senza tipi disponibili l'unica soluzione è lo zaino vuoto, ammissibile per ogni capacità e di profitto $0$.
Uno zaino limitato (BKP) si può trasformare in uno zaino 0-1 con $\sum_j b_j$ oggetti, uno per copia. Quanti passi esegue la PD del KP sull'istanza trasformata, con capacità $c$?
$\Theta(2^{\sum_j b_j})$, esponenziale
$\Theta(c\,b_{\max})$, indipendente da $n$
$\Theta(c\sum_j b_j)$, al più $\Theta(nc\,b_{\max})$ come la PD diretta
$\Theta(nc)$, indipendente dalle copie
Spiegazione. La PD del KP fa $\Theta(n'c)$ passi con $n'=\sum_j b_j\le n\,b_{\max}$ oggetti: lo stesso ordine, nel caso peggiore, della PD diretta del BKP.
Nello zaino limitato (BKP: tipo $j$ con peso $w_j$ e $b_j$ copie, capacità $c$), quando il limite $b_j$ non vincola mai la soluzione?
Quando $b_jw_j<c$
Quando $b_j\ge\lfloor c/w_j\rfloor$: più copie non entrerebbero comunque
Quando $b_j=1$
Quando $b_j\le\lfloor c/w_j\rfloor$
Spiegazione. Con $b_j\ge\lfloor c/w_j\rfloor$ la capacità impone già $x_j\le\lfloor c/w_j\rfloor$: se vale per ogni tipo, il BKP è uno zaino illimitato.
Nella PD per lo zaino limitato (BKP) la ricorrenza prova $d=0,\dots,\min\{b_j,\lfloor k/w_j\rfloor\}$ copie del tipo $j$. A che cosa si riduce se $b_j=1$ per ogni tipo?
Alla PD dello zaino 0-1: $v(j,k)=\max\{v(j-1,k),\ p_j+v(j-1,k-w_j)\}$
Alla PD dello zaino illimitato: $v(j,k)=\max\{v(j-1,k),\ p_j+v(j,k-w_j)\}$
Alla PD del subset sum, con valori booleani
A una ricorrenza con un solo termine, $v(j-1,k)$
Spiegazione. Con $b_j=1$ restano le scelte $d=0$ e $d=1$, cioè escludere o prendere l'oggetto $j$, e la riga successiva parte da $j-1$ in entrambi i casi.
Nello zaino limitato (BKP) una soluzione è un vettore $(x_1,\dots,x_n)$ con $0\le x_j\le b_j$ intero e $\sum_jw_jx_j\le c$. Con $n=3$ tipi e $b=(1,2,4)$, quanti vettori candidati ci sono (prima di controllare la capacità)?
$30$
$128$
$7$
$8$
Spiegazione. $(b_1+1)(b_2+1)(b_3+1)=2\cdot3\cdot5=30$. $2^7=128$ tratterebbe le $7$ copie come oggetti distinti.
La PD per lo zaino limitato (BKP) esegue $\Theta(nc\,b_{\max})$ passi, con $b_{\max}=\max_jb_j$. Perché si può supporre $b_{\max}\le c$ senza perdere generalità?
Perché nel BKP vale sempre $b_j=1$
Perché la PD ignora i tipi con $b_j>c$
Non si può: $b_{\max}$ può superare $c$ e il bound cresce
Sostituire $b_j$ con $\min\{b_j,\lfloor c/w_j\rfloor\}$ non cambia il problema, perché più copie non entrano
Spiegazione. Con $w_j\ge1$ al più $\lfloor c/w_j\rfloor\le c$ copie del tipo $j$ stanno nello zaino; dopo la riduzione il bound $\Theta(nc\,b_{\max})$ è al più $\Theta(nc^2)$.
Uno zaino limitato con $b=(1,2,4)$ copie disponibili dei tre tipi si può trasformare in uno zaino 0/1 elencando ogni copia come oggetto a sé. Quanti oggetti ha lo zaino 0/1 equivalente?
$3$
$8$
$30$
$7$
Spiegazione. $1+2+4=7$ oggetti; la trasformazione è corretta ma conta più volte soluzioni equivalenti, da cui l'interesse per una PD sul BKP.
Nella PD per lo zaino limitato, per ogni coppia (tipo $j$, capacità $k$) il ciclo più interno prova $d=0,1,\dots,\min\{b_j,\lfloor k/w_j\rfloor\}$ copie. Con $k=7$, $w_j=2$ e $b_j=5$, quante iterazioni esegue?
$3$
$8$
$4$
$6$
Spiegazione. $\min\{5,\lfloor7/2\rfloor\}=3$, quindi $d=0,1,2,3$: $4$ iterazioni. Nel caso peggiore sono $b_{\max}+1$ per coppia, da cui $\Theta(nc\,b_{\max})$.
Lo zaino limitato (BKP) ha $n$ tipi, al più $b_j$ copie del tipo $j$, capacità $c$ e $b_{\max}=\max_j b_j$. Quanti passi esegue la PD che prova ogni numero di copie?
$\Theta(n\,b_{\max})$
$\Theta(c\,b_{\max}^{\,n})$
$\Theta(nc\,b_{\max})$
$\Theta(nc)$
Spiegazione. $(n+1)(c+1)$ celle, ciascuna con fino a $b_{\max}+1$ confronti.
Nel subset sum (interi $w_1,\dots,w_n$, obiettivo $c$), la PD calcola $r(j,k)$, vero se un sottoinsieme di $\{w_1,\dots,w_j\}$ ha somma esattamente $k$. Quali sono i casi base?
$r(j,0)=\textit{true}$ per ogni $j$, e $r(0,k)=\textit{false}$ per $k\ge 1$
$r(j,0)=\textit{false}$ per ogni $j$, e $r(0,k)=\textit{true}$ per $k\ge 1$
$r(0,k)=\textit{true}$ per ogni $k$
$r(j,0)=\textit{false}$ e $r(0,k)=\textit{false}$
Spiegazione. Il valore $0$ si ottiene sempre con il sottoinsieme vuoto; senza oggetti nessun valore positivo è raggiungibile. Con $r(j,0)=\textit{false}$ nessuna cella diventerebbe vera.
Nel subset sum (interi $w_1,\dots,w_n$, obiettivo $c$), $r(j,k)$ è vero se un sottoinsieme di $\{w_1,\dots,w_j\}$ ha somma esattamente $k$. Calcolata la tabella, dove si legge la risposta?
Nella cella $r(c,n)$
In una qualsiasi cella vera della colonna $c$
Nell'ultima cella vera della riga $n$
Nella cella $r(n,c)$
Spiegazione. La risposta è $r(n,c)$; una cella vera in un'altra colonna dice solo che è raggiungibile un altro valore. Se $r(n,c)$ è falsa non c'è nulla da ricostruire.
Nel subset sum (interi $w_1,\dots,w_n$, obiettivo $c$: esiste un sottoinsieme di somma esattamente $c$?), quanti passi esegue la PD con la tabella $r(j,k)$?
$\Theta(2^n)$
$\Theta(n\log c)$
$\Theta(nc)$
$\Theta(c^2)$
Spiegazione. La tabella ha $(n+1)(c+1)$ celle, ciascuna calcolata in tempo costante: $\Theta(nc)$, un tempo pseudo-polinomiale.
Subset sum con pesi $w=(2,2,2)$ e obiettivo $c=5$: $r(j,k)$ è vero se un sottoinsieme dei primi $j$ pesi ha somma esattamente $k$. Quanto vale $r(3,5)$?
Falso: le somme raggiungibili sono $0,2,4,6$
Vero: $5\le 6$
Vero: $2+2+1$
Falso: la tabella non contiene la colonna $5$
Spiegazione. Con pesi tutti pari ogni somma è pari, quindi $5$ non è raggiungibile. La colonna $5$ esiste ($k=0,\dots,c$) e contiene solo valori falsi.
Nella PD per il subset sum, $r(j,k)=r(j-1,k)\lor r(j-1,k-w_j)$ (il secondo termine solo se $w_j\le k$). Che cosa rappresenta il termine $r(j-1,k-w_j)$?
La scelta di non usare il peso $w_j$
La scelta di usare due volte il peso $w_j$
Il controllo che $k$ non superi l'obiettivo $c$
La scelta di usare il peso $w_j$: il resto $k-w_j$ va ottenuto con i primi $j-1$ pesi
Spiegazione. Se $w_j$ fa parte del sottoinsieme, i pesi precedenti devono sommare a $k-w_j$; $r(j-1,k)$ è invece la scelta di escluderlo. Ogni peso si usa al più una volta.
Nella PD per il subset sum ($r(j,k)$ vero se un sottoinsieme dei primi $j$ pesi ha somma $k$), con $r(n,c)$ vero, come si ricostruisce un sottoinsieme di somma $c$ partendo da $(j,k)=(n,c)$?
Se $r(j-1,k)$ è vero si prende $w_j$; altrimenti lo si esclude
Si prende il peso più grande e si ricomincia con $c-w_{\max}$
Se $r(j-1,k)$ è vero si esclude $w_j$; altrimenti si prende $w_j$ e $k\leftarrow k-w_j$; poi $j\leftarrow j-1$
Si prendono i pesi $w_j$ in ordine finché la somma non supera $c$
Spiegazione. Se $k$ si ottiene già senza $w_j$, si può escluderlo; altrimenti la cella è vera grazie a $r(j-1,k-w_j)$ e $w_j$ va preso. Si arriva a $k=0$.
Subset sum con pesi $w=(4,6,9)$ e obiettivo $c=12$. Con la PD si calcola $r(3,k)$ per $k=0,\dots,12$ ($r(j,k)$ vero se un sottoinsieme dei primi $j$ pesi ha somma esattamente $k$). Qual è il più grande $k\le 12$ con $r(3,k)$ vero?
$13$
$10$
$12$
$9$
Spiegazione. Le somme raggiungibili sono $0,4,6,9,10,13,15,19$; fra quelle non superiori a $12$ la più grande è $10=4+6$. $13=4+9$ supera l'obiettivo.
La PD per il subset sum si può implementare con un solo vettore $r[0..c]$, aggiornato peso per peso con $r[k]\leftarrow r[k]\lor r[k-w_j]$. In quale ordine si scorrono le somme $k$?
Da $c$ a $w_j$, in modo decrescente, per non usare due volte lo stesso peso
Da $w_j$ a $c$, in modo crescente, per leggere celle già aggiornate
In qualsiasi ordine, perché l'operazione è un «or»
Solo le somme multiple di $w_j$
Spiegazione. Scorrendo in modo crescente, $r[k-w_j]$ potrebbe essere già vero grazie a $w_j$ stesso, che verrebbe usato più volte: è l'ordine dello zaino illimitato, non del subset sum.
Nel subset sum (pesi $w_1,\dots,w_n$, obiettivo $c$), la PD riempie la tabella $r(j,k)$ per $j=0,\dots,n$ e $k=0,\dots,c$. Quante celle ha con $n=5$ e $c=20$?
$100$
$105$
$32$
$126$
Spiegazione. $(n+1)(c+1)=6\cdot 21=126$. $2^5=32$ conta i sottoinsiemi; $100$ e $105$ dimenticano la riga $0$ o la colonna $0$.
La PD per il subset sum esegue $\Theta(nc)$ passi con $n$ pesi e obiettivo $c$. Perché il subset sum resta NP-completo?
Perché il numero di sottoinsiemi è $2^n$, e la PD li elenca tutti
Perché la tabella ha valori booleani invece che interi
$c$ si scrive con circa $\log_2 c$ cifre, e $\Theta(nc)$ è esponenziale in quel numero di cifre
Perché la PD è corretta solo per pesi distinti
Spiegazione. Il tempo è polinomiale nel valore di $c$ ma non nella lunghezza dell'input: è un algoritmo pseudo-polinomiale, e il subset sum è NP-completo in senso debole.
Il subset sum (pesi $w_j$, obiettivo $c$) è il problema dello zaino 0-1 con profitti $p_j=w_j$ e capacità $c$. Con la PD del KP, $v(n,c)$ è il massimo peso di un sottoinsieme che non supera $c$. Come si legge la risposta al subset sum?
È sì se e solo se $v(n,c)=\sum_j w_j$
È sì se e solo se $v(n,c)=c$
È sì se e solo se $v(n,c)\ge 1$
È sì se e solo se $v(n,c)\le c$
Spiegazione. Un sottoinsieme di somma esattamente $c$ esiste se e solo se il massimo peso non superiore a $c$ vale proprio $c$; $v(n,c)\le c$ vale sempre.
La PD per il subset sum (SSP: esiste un sottoinsieme di pesi $w_j$ di somma esattamente $c$?) riempie una tabella sugli oggetti e sui valori $0,\dots,c$. Quanti passi esegue nel caso peggiore, con $n$ oggetti?
$\Theta(nc)$, come la PD dello zaino 0/1
$\Theta(2^n)$
$\Theta(n\log c)$
$\Theta(c^2)$
Spiegazione. Una cella per ogni coppia (oggetto, valore) con un numero costante di operazioni: $\Theta(nc)$, pseudo-polinomiale come per il KP; la ricostruzione aggiunge $\Theta(n)$ passi.
La PD per il subset sum riempie una tabella con una riga per ogni prefisso di oggetti $0,1,\dots,n$ e una colonna per ogni valore $0,\dots,c$. Con $n=4$ e $c=10$, quante celle ha?
$44$
$16$
$55$
$40$
Spiegazione. $(4+1)(10+1)=55$ celle, ciascuna calcolata in tempo costante: $\Theta(nc)$.
Dopo aver riempito la tabella della PD del subset sum, si ricostruisce un sottoinsieme di somma $c$ risalendo dalla cella $(n,c)$. Quanti passi richiede la ricostruzione?
$\Theta(2^n)$
$\Theta(n)$: un passo per oggetto
$\Theta(nc)$
$\Theta(c)$
Spiegazione. Per ogni oggetto, dall'ultimo al primo, si decide se è stato usato guardando una cella della riga precedente.
Il subset sum chiede se un sottoinsieme ha peso esattamente $c$. Sia $z$ il valore ottimo dello zaino 0/1 con $p_j=w_j$ e capacità $c$. Quando la risposta è «sì»?
Se e solo se $z\ge c/2$
Se e solo se $z<c$
Mai: i problemi non sono legati
Se e solo se $z=c$
Spiegazione. Con $p_j=w_j$ il profitto è il peso: il massimo peso non oltre $c$ vale $c$ esattamente quando un sottoinsieme pesa $c$.
Nello zaino a scelta multipla (MCKP: $q$ classi, si sceglie esattamente un oggetto per classe, capacità $c$), $v(h,k)$ è il valore ottimo con le classi $1,\dots,h$ e capacità $k$. Quanto valgono $v(0,k)$ e il valore di un sottoproblema senza soluzioni ammissibili?
$v(0,k)=0$ per ogni $k$; senza soluzioni ammissibili vale $0$
$v(0,k)=-\infty$ per $k\ge 1$; senza soluzioni ammissibili vale $0$
$v(0,k)=k$ per ogni $k$; senza soluzioni ammissibili vale $+\infty$
$v(0,k)=0$ per ogni $k$; senza soluzioni ammissibili vale $-\infty$
Spiegazione. Senza classi l'insieme vuoto è ammissibile per ogni capacità; $-\infty$ segna le sottoistanze in cui una classe non ha oggetti che entrano. Con $0$ si salterebbe una classe.
Nello zaino a scelta multipla (MCKP, classi $\mathscr{J}_1,\dots,\mathscr{J}_q$) la ricorrenza è $v(h,k)=\max_{j\in\mathscr{J}_h:\,w_j\le k}\{p_j+v(h-1,k-w_j)\}$. Che cosa manca rispetto alla ricorrenza del KP 0/1?
Il caso base $v(0,k)$, perché la prima classe lo sostituisce
Il controllo $w_j\le k$, perché la classe fissa il peso
Il termine $v(h-1,k)$, perché ogni classe dà esattamente un oggetto
Il termine $v(h-1,k)$, perché nessun oggetto ha peso nullo
Spiegazione. Nel KP si può non prendere un oggetto; nell'MCKP da ogni classe si prende esattamente un oggetto, quindi l'opzione «nessuno» non compare.
Nello zaino a scelta multipla (MCKP) gli $n$ oggetti sono ripartiti nelle classi $\mathscr{J}_1,\dots,\mathscr{J}_q$ e la capacità è $c$. Quanti passi esegue la PD con stadi le classi?
Zaino a scelta multipla (MCKP): classi $\mathscr{J}_1=\{1,2\}$, $\mathscr{J}_2=\{3,4\}$, profitti $p=(3,5,4,6)$, pesi $w=(2,4,1,3)$, capacità $c=5$; si sceglie esattamente un oggetto per classe. Con $v(h,k)=\max_{j\in\mathscr{J}_h:\,w_j\le k}\{p_j+v(h-1,k-w_j)\}$, quanto vale $v(2,5)$?
$7$
$10$
$9$
$11$
Spiegazione. Le coppie ammissibili sono $\{1,3\}$ (peso $3$, profitto $7$), $\{1,4\}$ e $\{2,3\}$ (peso $5$, profitto $9$); $\{2,4\}$ pesa $7$. Il valore $11=5+6$ ignora la capacità.
Zaino a scelta multipla (MCKP) con classi $\mathscr{J}_1=\{1,2\}$ (pesi $2$ e $4$) e $\mathscr{J}_2=\{3,4\}$ (pesi $1$ e $3$); si sceglie esattamente un oggetto per classe. Che cosa dà la PD con capacità $c=2$?
Il profitto dell'oggetto più leggero della classe $2$
$v(2,2)=-\infty$: non c'è nessuna soluzione ammissibile
$v(2,2)=0$: non si sceglie nessun oggetto
Il profitto dell'oggetto più leggero della classe $1$
Spiegazione. Servono almeno $2+1=3$ unità di capacità, una per classe: con $c=2$ nessuna scelta è ammissibile. In un problema di massimo il valore $-\infty$ segnala l'inammissibilità.
Nella PD per lo zaino a scelta multipla (MCKP), $v(h,k)=\max_{j\in\mathscr{J}_h:\,w_j\le k}\{p_j+v(h-1,k-w_j)\}$. Quanti sottoproblemi genera al più lo stato $(h,k)$?
$|\mathscr{J}_h|$, uno per ogni oggetto della classe $h$ che entra
$2$, come nel KP 0/1
$|\mathscr{J}_h|+1$, contando la scelta di nessun oggetto
$q$, uno per ogni classe
Spiegazione. Ogni oggetto della classe $h$ con $w_j\le k$ è una scelta possibile; non c'è la scelta «nessun oggetto», perché ogni classe dà esattamente un oggetto.
Nella PD per lo zaino a scelta multipla (MCKP), $s(h,k)$ è l'oggetto della classe $h$ che realizza il massimo in $v(h,k)$. Come si ricostruisce una soluzione ottima partendo da $(q,c)$?
Si sceglie $s(q,c)$ e lo si ripete per ogni classe
Si sceglie in ogni classe l'oggetto di profitto massimo
Si sceglie $j=s(h,k)$ e si pone $h\leftarrow h-1$ senza cambiare $k$
Si sceglie $j=s(h,k)$, si pone $k\leftarrow k-w_j$ e $h\leftarrow h-1$, fino a $h=0$
Spiegazione. Ogni passo fissa l'oggetto di una classe e riduce la capacità residua del suo peso; si ottiene esattamente un oggetto per classe.
Nella PD per lo zaino a scelta multipla (MCKP) con $q$ classi e capacità $c$, la tabella $v(h,k)$ ha una riga per ogni $h=0,\dots,q$ e una colonna per ogni $k=0,\dots,c$. Quante celle ha con $q=3$ e $c=15$?
$96$
$45$
$64$
$48$
Spiegazione. $(q+1)(c+1)=4\cdot16=64$. Le righe sono le classi, non gli oggetti: per questo i passi sono $\Theta(c\sum_h|\mathscr{J}_h|)=\Theta(nc)$.
Zaino a scelta multipla (MCKP): la classe $\mathscr{J}_1$ contiene gli oggetti $(p,w)=(3,2)$ e $(5,4)$; si sceglie esattamente un oggetto per classe. Quanto vale $v(1,3)$, il valore ottimo con la sola classe $1$ e capacità $3$?
$0$
$3$
$5$
$-\infty$
Spiegazione. Con capacità $3$ entra solo l'oggetto di peso $2$: $v(1,3)=3$. Per $k<2$ la classe non dà nessun oggetto e $v(1,k)=-\infty$; il valore $0$ corrisponderebbe a non scegliere nulla, vietato.
Nella PD per lo zaino a scelta multipla (MCKP), quanto vale il caso base $v(0,k)$, con nessuna classe considerata e capacità $k\ge 0$?
$-\infty$ per ogni $k\ge 1$
$-\infty$ per $k=0$ e $0$ altrimenti
$k$ per ogni $k$
$0$ per ogni $k$: la scelta vuota è ammissibile quando non ci sono classi
Spiegazione. Con zero classi non c'è niente da scegliere, e la capacità può restare inutilizzata. Il valore $-\infty$ compare solo quando una classe non ha oggetti che entrano.
Nella PD per lo zaino a scelta multipla (MCKP) le classi sono gli stadi della ricorsione. Che cosa succede al valore ottimo se si cambia l'ordine delle classi?
Cambia, a meno di ordinare le classi per profitto
Non cambia, ma la PD diventa scorretta
Non cambia: cambiano solo i valori intermedi della tabella
Cambia, perché la prima classe ha più capacità disponibile
Spiegazione. Una soluzione è un oggetto per classe, e il suo profitto e il suo peso non dipendono dall'ordine; ogni ordine dà una ricorrenza corretta con lo stesso valore finale.
La PD per lo zaino a scelta multipla (MCKP: $q$ classi $\mathscr{J}_h$, esattamente un oggetto per classe, capacità $c$) esegue $\Theta(c(|\mathscr{J}_1|+\dots+|\mathscr{J}_q|))$ passi. Con $3$ classi di $4$, $2$ e $6$ oggetti e $c=50$, di che ordine è il numero di passi?
$2^{12}$ volte una costante
$12\cdot50=600$ volte una costante
$4\cdot2\cdot6\cdot50=2400$ volte una costante
$3\cdot50=150$ volte una costante
Spiegazione. Per ogni classe e ogni capacità si provano gli oggetti della classe: in tutto $n\,c$ con $n=12$ oggetti. Il prodotto $4\cdot2\cdot6$ conta le scelte di un oggetto per classe, che la PD non enumera.
Dopo aver calcolato la tabella della PD per lo zaino a scelta multipla ($q$ classi, un oggetto per classe), quanti passi richiede la ricostruzione della soluzione?
$\Theta(qc)$
$\Theta(2^q)$
$\Theta(q)$: un passo per classe
$\Theta(n)$: un passo per oggetto
Spiegazione. Risalendo dalla capacità $c$ si legge, classe per classe, l'oggetto scelto: un passo per classe.
Nella PD per lo zaino a scelta multipla (MCKP) si pone $v(h,k)=-\infty$ quando nessun oggetto della classe $h$ entra. Su quale vincolo del problema si basa?
Da ogni classe si sceglie al più un oggetto
Gli oggetti sono in copie illimitate
La capacità va riempita esattamente
Da ogni classe si sceglie esattamente un oggetto
Spiegazione. Se una classe non può contribuire con un oggetto, il sottoproblema non ha soluzioni ammissibili: $-\infty$.
Lo zaino a scelta multipla ha $q$ classi $\mathscr{J}_h$, $n=\sum_h|\mathscr{J}_h|$ oggetti e capacità $c$. Quanti passi esegue la PD sulle classi, e quando l'istanza è inammissibile?
$\Theta(nc)$; se $v(q,c)=0$
$\Theta(n^2c)$; se $v(q,0)=-\infty$
$\Theta(nc)$; se $v(q,c)=-\infty$
$\Theta(qc)$; se $v(q,c)=0$
Spiegazione. Ogni cella $(h,k)$ guarda gli oggetti della classe $h$: in tutto $\Theta(c\sum_h|\mathscr{J}_h|)=\Theta(nc)$.
7. PD per il problema dello zaino multidimensionale (17)
Nello zaino multidimensionale (MDKP) ogni oggetto ha un vettore di pesi e lo zaino un vettore di capacità $\vet{c}$. Quante celle ha la tabella $v(j,\vet{k})$ della PD con $n=4$ oggetti e $\vet{c}=(5,4)$?
$50$
$150$
$120$
$45$
Spiegazione. Le celle sono $(n+1)\prod_d(c_d+1)=5\cdot 6\cdot 5=150$: un vettore di capacità residue per ogni $j\in\{0,\dots,n\}$.
Nello zaino multidimensionale (MDKP) l'oggetto $j$ ha pesi $w_{dj}$ nelle dimensioni $d=1,\dots,m$. Nella PD, quando l'oggetto $j$ «entra» nel vettore di capacità residue $\vet{k}$?
Quando $w_{dj}\le k_d$ per ogni dimensione $d$
Quando $w_{dj}\le k_d$ per almeno una dimensione $d$
Quando $\sum_d w_{dj}\le\sum_d k_d$
Quando $\max_d w_{dj}\le\min_d k_d$
Spiegazione. Il vettore $\vet{w}_j$ deve stare nel vettore $\vet{k}$ componente per componente; se l'oggetto è scelto, tutte le componenti di $\vet{k}$ diminuiscono.
Zaino multidimensionale (MDKP) con capacità $\vet c=(4,4)$ e tre oggetti: profitti $p=(5,4,3)$, pesi nella dimensione 1 $(3,1,2)$ e nella dimensione 2 $(1,3,2)$; ogni oggetto al più una volta. Quanto vale il valore ottimo $v(3,(4,4))$?
$5$
$7$
$9$
$12$
Spiegazione. $\{1,2\}$ pesa $(4,4)$ e vale $9$; $\{1,3\}$ pesa $5$ nella dimensione 1 e $\{2,3\}$ pesa $5$ nella dimensione 2. $7$ si ottiene guardando solo la dimensione 1 per $\{2,3\}$.
Nella PD per lo zaino multidimensionale (MDKP), $v(j,\vet k)$ è il massimo profitto con gli oggetti $1,\dots,j$ e il vettore di capacità residue $\vet k$; $\vet w_j$ è il vettore dei pesi dell'oggetto $j$. Quale ricorrenza è corretta?
$v(j,\vet k)=p_j+v(j-1,\vet k-\vet w_j)$ se $\sum_d w_{dj}\le\sum_d k_d$
$v(j,\vet k)=\max\{v(j-1,\vet k),\ p_j+v(j-1,\vet k-\vet w_j)\}$ se $\vet w_j\le\vet k$ componente per componente
$v(j,\vet k)=\max\{v(j-1,\vet k),\ p_j+v(j,\vet k-\vet w_j)\}$ se $\vet w_j\le\vet k$
Spiegazione. È la ricorrenza del KP con un vettore al posto della capacità: si prende l'oggetto solo se entra in ogni dimensione. Restare nella riga $j$ permetterebbe più copie.
Nella PD per lo zaino multidimensionale con $m=10$ dimensioni, tutte di capacità $100$, quanti vettori di capacità residue $\vet k$ ci sono per ogni oggetto?
$101^{10}$
$10\cdot 101$
$100^{10}$
$2^{10}$
Spiegazione. Ogni componente va da $0$ a $100$: $\prod_d(c_d+1)=101^{10}\approx 10^{20}$ stati per riga. È la maledizione della dimensionalità: il numero di stati cresce esponenzialmente con $m$.
Nella PD per lo zaino multidimensionale (MDKP), quanto vale il caso base $v(0,\vet k)$, senza oggetti e con vettore di capacità residue $\vet k\ge\vet 0$?
$-\infty$ per $\vet k\ne\vet 0$
$\sum_d k_d$
$+\infty$ per ogni $\vet k$
$0$ per ogni $\vet k$
Spiegazione. Senza oggetti la soluzione vuota è ammissibile per ogni vettore di capacità e vale $0$; lo zaino non deve essere riempito in nessuna dimensione.
Nella PD per lo zaino multidimensionale (MDKP), nella ricostruzione di una soluzione ottima da $(n,\vet c)$, come si aggiorna lo stato quando l'oggetto $j$ è scelto?
$j$ resta uguale e $\vet k\leftarrow\vet k-\vet w_j$
$j\leftarrow j-1$ e $\vet k$ resta uguale
$j\leftarrow j-1$ e $\vet k\leftarrow\vet k-\vet w_j$, cioè ogni componente diminuisce del peso dell'oggetto in quella dimensione
$j\leftarrow j-1$ e solo la prima componente di $\vet k$ diminuisce
Spiegazione. L'oggetto consuma capacità in tutte le dimensioni: si sottrae il suo vettore dei pesi e si passa all'oggetto precedente.
Lo zaino multidimensionale (MDKP) ha $m$ dimensioni, con un peso $w_{dj}$ e una capacità $c_d$ per dimensione. A che cosa si riduce con $m=1$, e che cosa diventa la sua PD?
Allo zaino multiplo, con un vettore di capacità
Allo zaino 0-1, con la PD $v(j,k)$ su una sola capacità
Allo zaino illimitato, con la PD $v(k)$
Al subset sum, con la PD booleana
Spiegazione. Con una dimensione resta un vincolo di capacità e la tabella $v(j,\vet k)$ diventa $v(j,k)$: la PD del KP è il caso $m=1$.
Nella PD per lo zaino multidimensionale (MDKP) con $n$ oggetti e capacità $c_1,\dots,c_m$, quanti passi si eseguono?
$\Theta\big(n\prod_d(c_d+1)\big)$: pseudo-polinomiale solo per $m$ fissato
$\Theta\big(n\sum_d c_d\big)$: pseudo-polinomiale per ogni $m$
$\Theta(nm)$: polinomiale
$\Theta(2^n)$: come la forza bruta
Spiegazione. Ogni cella $v(j,\vet k)$ si calcola con due termini, e le celle sono $(n+1)\prod_d(c_d+1)$; il prodotto rende il tempo esponenziale nel numero di dimensioni.
Nella PD per lo zaino multidimensionale (MDKP), la tabella $v(j,\vet k)$ ha una cella per ogni $j=0,\dots,n$ e ogni vettore $\vet 0\le\vet k\le\vet c$. Quante celle ha con $n=3$ e $\vet c=(4,4)$?
$75$
$48$
$64$
$100$
Spiegazione. $(n+1)(c_1+1)(c_2+1)=4\cdot5\cdot5=100$. $75$ dimentica la riga $j=0$; $48=4\cdot4\cdot3$ dimentica le capacità nulle.
Per lo zaino multidimensionale (MDKP) con due dimensioni di capacità $c_1$ e $c_2$ e $n$ oggetti, quanti passi esegue la PD, e come si confronta con la PD dello zaino 0-1 con capacità $c$?
$\Theta(n^2c_1c_2)$, perché le dimensioni sono due
$\Theta(nc_1)$, perché basta la dimensione più vincolante
$\Theta(n\,c_1c_2)$, contro $\Theta(nc)$: una seconda dimensione moltiplica il lavoro per la sua capacità
$\Theta(n(c_1+c_2))$, lo stesso ordine dello zaino 0-1
Spiegazione. Gli stati per riga sono $(c_1+1)(c_2+1)$, ciascuno con due termini. Usare solo la dimensione più vincolante darebbe un rilassamento, non il valore ottimo.
La PD per lo zaino multidimensionale (MDKP: $m$ capacità $c_d$) ha uno stato per ogni vettore di capacità $\vet k$, cioè $N=\prod_d(c_d+1)$ stati per oggetto. Con $m=2$, $\vet c=(10,20)$ e $n=5$ oggetti, quanti stati per oggetto ci sono?
$32$
$231$
$30$
$200$
Spiegazione. $N=(10+1)(20+1)=231$, e i passi sono $\Theta(m\,n\,N)$. $30$ somma le capacità, che è l'errore tipico: gli stati si moltiplicano.
La PD per lo zaino multidimensionale esegue $\Theta(m\,n\prod_{d=1}^m(c_d+1))$ passi. Sotto quale ipotesi questo numero è pseudo-polinomiale?
Se il numero $m$ di dimensioni è fissato: allora è $\Theta(n\prod_dc_d)$, polinomiale nei valori delle capacità
Sempre, per ogni $m$
Solo se tutte le capacità sono uguali
Solo se $n\le m$
Spiegazione. Con $m$ parte dell'input il prodotto delle capacità è esponenziale in $m$ anche con capacità piccole (per esempio $2^m$ con $c_d=1$): è la maledizione della dimensionalità.
Nella PD per lo zaino multidimensionale lo stato è un vettore di capacità $\vet k$, con $\prod_d(c_d+1)$ valori. Con $m=10$ dimensioni e tutte le capacità $c_d=1$, quanti stati ci sono per oggetto?
$11$
$100$
$1024$
$20$
Spiegazione. $2^{10}=1024$: anche con capacità minime il numero di stati cresce esponenzialmente con le dimensioni. È la maledizione della dimensionalità.
La PD per lo zaino multidimensionale (MDKP) con $m$ dimensioni e capacità $c_1,\dots,c_m$ esegue $\Theta(m\,n\prod_d(c_d+1))$ passi. Che cosa succede al crescere di $m$?
Il tempo diventa polinomiale
Il numero di stati non cambia
Gli stati crescono in modo esponenziale in $m$
Il tempo cresce in modo lineare in $m$
Spiegazione. Il prodotto delle $m$ capacità esplode: è la maledizione della dimensionalità.
Nello zaino con setup (KPS) gli oggetti sono in classi; usare la classe $h$ costa un profitto di setup $f_h$ e un peso di setup $s_h$. Nella PD, $v(h,k)$ è il valore ottimo con le classi $1,\dots,h$ e $u(h,\cdot,k)$ sono le righe della classe $h$ aperta. Come si paga il setup?
Una sola volta, nella riga $u(h,0,k)=v(h-1,k-s_h)-f_h$
Una volta per ogni oggetto scelto della classe, sottraendo $f_h$ e $s_h$
Una sola volta, nella riga $v(h,k)$, se $v(h,k)>v(h-1,k)$
Una sola volta, alla fine, sottraendo $\sum_h f_h$ da $v(q,c)$
Spiegazione. La riga $u(h,0,\cdot)$ apre la classe: riserva il peso di setup $s_h$ e sottrae il costo $f_h$; le righe successive sono la ricorrenza del KP sugli oggetti della classe.
Nella PD dello zaino con setup (KPS), $v(h,k)$ è il valore ottimo con le classi $1,\dots,h$ e capacità $k$, e $u(h,t_h,k)$ quello con la classe $h$ aperta (setup pagato) dopo i suoi $t_h$ oggetti. Come si calcola $v(h,k)$ per $h\ge 1$?
$v(h,k)=v(h-1,k)+u(h,t_h,k)$
$v(h,k)=\max\{v(h-1,k),\ u(h,0,k)\}$
$v(h,k)=u(h,t_h,k)$
$v(h,k)=\max\{v(h-1,k),\ u(h,t_h,k)\}$
Spiegazione. Per ogni classe si confrontano le due opzioni: non usarla (valore $v(h-1,k)$) o aprirla e scegliere i suoi oggetti (valore $u(h,t_h,k)$).
Nella PD dello zaino con setup (KPS: la classe $h$ ha costo di setup $f_h$ e peso di setup $s_h$), perché le righe degli oggetti della classe $h$ non partono da $v(h-1,k)$, il valore ottimo con le classi precedenti?
Perché $v(h-1,k)$ non è ancora calcolato a quel punto
Perché $v(h-1,k)$ vale $-\infty$ quando $s_h>0$
Perché si sceglierebbero oggetti della classe senza pagarne il setup
Perché il setup verrebbe pagato una volta per ogni oggetto scelto
Spiegazione. Le righe di una classe aperta partono da $u(h,0,k)=v(h-1,k-s_h)-f_h$, che ha già pagato il setup una volta.
Zaino con setup (KPS) con una sola classe: costo di setup $f=3$, peso di setup $s=2$, oggetti $(p,w)=(5,2)$ e $(4,3)$, capacità $c=6$. Il setup si paga una volta se si sceglie almeno un oggetto della classe. Quanto vale il valore ottimo?
$5$
$6$
$0$
$2$
Spiegazione. Aperta la classe restano $6-2=4$ unità: entra solo $(5,2)$, perché i due oggetti pesano $5$. Il valore è $5-3=2>0$. $5$ dimentica il costo di setup, $6=9-3$ dimentica il peso di setup.
Nella PD dello zaino con setup (KPS), $u(h,0,k)=v(h-1,k-s_h)-f_h$ è il valore con la classe $h$ aperta (setup pagato) e nessun suo oggetto ancora scelto. Che cosa vale se $k<s_h$?
$-f_h$: si paga il setup senza capacità
$v(h-1,k)$: si ignora il setup
$-\infty$: la classe non si può aprire perché il peso di setup non entra
$0$: la classe resta chiusa
Spiegazione. Aprire la classe consuma $s_h$ unità di capacità; se non ci sono, lo stato non è raggiungibile e $-\infty$ lo esclude dal massimo.
Nella PD dello zaino con setup (KPS), aprire la classe $h$ senza sceglierne oggetti dà $u(h,0,k)=v(h-1,k-s_h)-f_h$. Perché questo stato non migliora mai $v(h,k)=\max\{v(h-1,k),\ u(h,t_h,k)\}$ da solo?
Perché $v(h-1,k-s_h)-f_h\le v(h-1,k)$: si paga il setup e si perde capacità senza guadagnare nulla
Perché $u(h,0,k)$ vale sempre $-\infty$
Perché la classe $h$ ha almeno un oggetto di profitto positivo
Perché $f_h$ è sempre maggiore di $s_h$
Spiegazione. $v(h-1,\cdot)$ è non decrescente nella capacità e $f_h\ge 0$: una classe aperta ma vuota non conviene. Lo stato serve come punto di partenza delle righe degli oggetti della classe.
Nella PD dello zaino con setup (KPS) con $q$ classi, $n$ oggetti in tutto e capacità $c$, ci sono una riga $v(h,\cdot)$ per classe e una riga $u(h,i,\cdot)$ per ogni oggetto e per l'apertura di ogni classe. Quanti passi si eseguono?
$\Theta(nqc)$
$\Theta(2^qnc)$
$\Theta(nc^2)$
$\Theta((n+q)c)$
Spiegazione. Le righe sono $O(n+q)$, ognuna con $c+1$ celle calcolate in tempo costante: $\Theta((n+q)c)$, pseudo-polinomiale come la PD del KP.
Nella PD dello zaino con setup (KPS), nella ricostruzione di una soluzione ottima, che cosa si decide nello stato $(h,k)$ prima di guardare gli oggetti della classe $h$?
Quante classi aprire in tutto
Se il peso di setup $s_h$ supera la capacità totale $c$
Se la classe $h$ è aperta, confrontando $v(h,k)$ con $v(h-1,k)$
Quale oggetto della classe $h$ ha profitto massimo
Spiegazione. Se $v(h,k)=v(h-1,k)$ la classe può restare chiusa e si passa a $h-1$ con la stessa capacità; altrimenti si scorrono le righe $u(h,\cdot,\cdot)$ degli oggetti e alla fine si toglie il peso di setup.
Nello zaino con setup (KPS), la classe $h$ ha costo di setup $f_h$ e i suoi oggetti hanno profitto totale $P_h$. In quale caso la classe non viene mai aperta in una soluzione ottima, qualunque sia la capacità?
Quando la classe ha un solo oggetto
Quando $f_h\ge P_h$: anche prendendo tutti gli oggetti il guadagno netto non è positivo
Quando $f_h\le P_h$
Quando il peso di setup è nullo
Spiegazione. Aprire la classe rende al più $P_h-f_h\le 0$ e consuma capacità: lasciarla chiusa non peggiora mai la soluzione.
A che cosa si riduce lo zaino con setup (KPS) quando tutti i costi e i pesi di setup sono nulli ($f_h=s_h=0$)?
Allo zaino 0-1 sugli stessi oggetti
Allo zaino a scelta multipla, un oggetto per classe
Allo zaino illimitato
Allo zaino multiplo, uno zaino per classe
Spiegazione. Aprire una classe non costa nulla, quindi le classi non contano: restano gli oggetti, ciascuno scelto al più una volta, con una sola capacità.
Nella PD dello zaino con setup (KPS), dopo l'apertura della classe $h$ le righe $u(h,i,k)$ scorrono i suoi oggetti. Quale ricorrenza usano, con $j$ l'$i$-esimo oggetto della classe?
$u(h,i,k)=\max\{v(h-1,k),\ p_j+v(h-1,k-w_j)\}$
$u(h,i,k)=p_j-f_h+u(h,i-1,k-w_j-s_h)$
$u(h,i,k)=\max\{u(h,i-1,k),\ p_j+u(h,i,k-w_j)\}$
$u(h,i,k)=\max\{u(h,i-1,k),\ p_j+u(h,i-1,k-w_j)\}$, come nel KP 0/1
Spiegazione. Dentro la classe aperta ogni oggetto si prende o no, una volta sola; il setup è già pagato nella riga $u(h,0,\cdot)$, quindi non compare più.
La PD per lo zaino con setup (KPS: $n$ oggetti in $q$ classi con costo e peso di setup, capacità $c$) esegue $\Theta(nc)$ passi. Che cosa aggiungono i setup rispetto alla PD dello zaino 0/1?
Nulla: i setup si ignorano
Un numero di righe proporzionale a $q$ (apertura e chiusura di ogni classe), assorbito da $\Theta(nc)$ perché $q\le n$
Un fattore $2^q$ per le classi attivate
Un fattore $q$, cioè $\Theta(nqc)$
Spiegazione. Per ogni classe la tabella ha due righe in più (classe chiusa o attivata) oltre alle righe degli oggetti: $\Theta((n+2q)c)=\Theta(nc)$.
La PD per lo zaino con setup esegue $S(n,q,c)=4n(c+1)+8q(c+1)+2n+q+2c+4$ passi. Quanti sono con $n=4$ oggetti, $q=2$ classi e $c=5$?
$96$
$192$
$120$
$216$
Spiegazione. $4\cdot4\cdot6=96$, $8\cdot2\cdot6=96$, poi $8+2+10+4$: $216$. Le righe dei setup contano quanto quelle degli oggetti, ma restano $\Theta(nc)$.
Nello zaino multiplo (MKP) ci sono $m$ zaini di capacità $c_1,\dots,c_m$ e ogni oggetto va in al più uno zaino. Nella PD, se l'oggetto $j$ è inserito nello zaino $i$, come cambia il vettore $\vet{k}$ delle capacità residue?
Diminuiscono tutte le componenti, di $w_j$
Diminuiscono tutte le componenti, di $w_j/m$
Non cambia: le capacità si controllano alla fine
Diminuisce solo la componente $k_i$, di $w_j$
Spiegazione. L'oggetto va in un solo zaino: $\vet{k}-w_j\vet{e}_i$. Diminuire tutte le componenti è la regola dello zaino multidimensionale.
Nello zaino multiplo (MKP: $m$ zaini, ogni oggetto in al più uno zaino), la PD ha stati $(j,\vet{k})$ con $\vet{k}$ vettore delle capacità residue. Quanti sottoproblemi genera al più lo stato $(j,\vet{k})$?
$2$: l'oggetto $j$ è scelto o no, indipendentemente dallo zaino
$m$: l'oggetto $j$ va sempre in uno degli zaini in cui entra
$m+1$: l'oggetto $j$ resta fuori o va in uno degli zaini in cui entra
$2^m$: uno per ogni sottoinsieme di zaini in cui mettere l'oggetto $j$
Spiegazione. L'opzione «oggetto fuori» ($v(j-1,\vet{k})$) è sempre presente; in più c'è un'opzione per ogni zaino $i$ con $w_j\le k_i$.
Nello zaino multiplo (MKP: $m$ zaini di capacità $c_1,\dots,c_m$, ogni oggetto in al più uno zaino), che cosa dà il valore ottimo del KP con un solo zaino di capacità $c_1+\dots+c_m$?
Il valore di una soluzione ammissibile dell'MKP
Un upper bound: la soluzione può non essere divisibile fra gli zaini
Un lower bound: la soluzione si divide sempre fra gli zaini
Il valore ottimo dell'MKP, perché le capacità si sommano
Spiegazione. Ogni soluzione dell'MKP è ammissibile per il KP con capacità totale, non viceversa: si ottiene un rilassamento, quindi un upper bound.
Zaino multiplo (MKP) con due zaini di capacità $c_1=c_2=3$ e tre oggetti $(p,w)=(4,2)$, $(4,2)$, $(5,3)$; ogni oggetto va in al più uno zaino. Quanto vale il valore ottimo?
$9$
$8$
$13$
$10$
Spiegazione. L'oggetto $3$ riempie uno zaino e uno dei primi due va nell'altro: $5+4=9$. I due oggetti di peso $2$ non stanno insieme in uno zaino di capacità $3$, quindi $13$ non è ammissibile.
Nella PD per lo zaino multiplo (MKP) con $m$ zaini, $v(j,\vet k)$ è il valore ottimo con gli oggetti $1,\dots,j$ e capacità residue $\vet k=(k_1,\dots,k_m)$, ed $\vet e_i$ è il vettore unitario dello zaino $i$. Quale ricorrenza è corretta?
Spiegazione. L'oggetto $j$ resta fuori oppure va in uno zaino $i$ in cui entra, e solo quella capacità diminuisce. Senza il termine $v(j-1,\vet k)$ ogni oggetto andrebbe inserito.
Nella PD per lo zaino multiplo (MKP) con zaini di capacità tutte uguali, gli stati $(j,\vet k)$ e $(j,\vet k')$ con $\vet k'$ permutazione di $\vet k$ hanno lo stesso valore. Come si può sfruttare?
Eliminando gli zaini vuoti dallo stato
Non si può: la PD deve distinguere gli zaini
Tenendo solo i vettori ordinati, per esempio con componenti non crescenti
Usando una sola capacità, la somma delle componenti
Spiegazione. Gli zaini identici sono intercambiabili, quindi basta un rappresentante per ogni classe di vettori permutati: il numero di stati diminuisce, anche se resta esponenziale in $m$.
Nella PD per lo zaino multiplo (MKP), per ricostruire una soluzione ottima si memorizza per ogni stato $(j,\vet k)$ un valore $s(j,\vet k)$. Che cosa conviene memorizzare?
Solo se l'oggetto $j$ è scelto o no
Il profitto totale dello zaino più pieno
Il vettore $\vet k$ dello stato successivo
L'indice dello zaino in cui va l'oggetto $j$, con $0$ se resta fuori
Spiegazione. Con l'indice $i$ si aggiorna $\vet k\leftarrow\vet k-w_j\vet e_i$ e si sa in quale zaino va l'oggetto; «scelto o no» non basta, perché la soluzione dell'MKP dice anche dove.
Lo zaino multiplo (MKP) ha $m$ zaini di capacità $c_1,\dots,c_m$ e ogni oggetto va in al più uno zaino. A che cosa si riduce con $m=1$?
Allo zaino multidimensionale con una dimensione per oggetto
Al bin packing con un contenitore
Allo zaino 0-1 con capacità $c_1$
Allo zaino illimitato con capacità $c_1$
Spiegazione. Con un solo zaino ogni oggetto è dentro o fuori, con una capacità: è il KP, e la PD con il vettore $\vet k$ diventa quella con la capacità $k$.
Nella PD per lo zaino multiplo (MKP), la tabella $v(j,\vet k)$ ha una cella per ogni $j=0,\dots,n$ e ogni vettore $\vet 0\le\vet k\le\vet c$. Quante celle ha con $n=4$ oggetti e capacità $\vet c=(3,5)$?
$40$
$120$
$96$
$45$
Spiegazione. $(n+1)(c_1+1)(c_2+1)=5\cdot4\cdot6=120$. $96$ dimentica la riga $j=0$; $45=5\cdot(3+5+1)$ somma le capacità invece di moltiplicarle.
Nella PD per lo zaino multiplo (MKP) con $m$ zaini, ogni stato $(j,\vet k)$ genera al più $m+1$ sottoproblemi. Quanti passi esegue la PD con $n$ oggetti e capacità $c_1,\dots,c_m$?
$\Theta\big(nm\prod_i(c_i+1)\big)$
$\Theta\big(n\sum_i c_i\big)$
$\Theta\big(n(m+1)\big)$
$\Theta\big(2^m n\big)$
Spiegazione. Le celle sono $(n+1)\prod_i(c_i+1)$ e ognuna confronta $m+1$ termini. Il tempo è pseudo-polinomiale solo per $m$ fissato.
La PD per gli zaini multipli (MKP: $m$ zaini di capacità $c_i$) usa come stato il vettore delle capacità residue, $N=\prod_i(c_i+1)$ stati per oggetto, e $\Theta(m\,n\,N)$ passi. Con $m=2$ zaini di capacità $5$ e $7$, quanti stati per oggetto ci sono?
$35$
$12$
$48$
$13$
Spiegazione. $(5+1)(7+1)=48$. Con un solo zaino di capacità $12$ gli stati sarebbero $13$: dividere la capacità in due zaini moltiplica gli stati.
La PD per gli zaini multipli esegue $S=3m\,nN+2nN+2N+n+2$ passi, con $N=\prod_i(c_i+1)$. Quanti sono con $m=2$ zaini di capacità $1$ e $2$ e $n=2$ oggetti?
$72$
$96$
$60$
$112$
Spiegazione. $N=2\cdot3=6$: $3\cdot2\cdot2\cdot6=72$, $2\cdot2\cdot6=24$, $2\cdot6=12$, poi $2+2$: $112$.
Nella PD per gli zaini multipli, con $m$ zaini, lo stato è il vettore delle capacità residue. Con $m=3$ zaini di capacità $2$, quanti stati ci sono per oggetto?
$7$
$8$
$27$
$9$
Spiegazione. $(2+1)^3=27$: un valore di capacità residua per zaino, combinati in tutti i modi.
Una capacità totale di $12$ si divide fra $m$ zaini uguali. Quanti stati $\prod_i(c_i+1)$ ha la PD per gli zaini multipli con $m=1$ (capacità $12$) e con $m=3$ (capacità $4,4,4$)?
$13$ e $39$
$13$ e $125$
$13$ e $15$
$12$ e $64$
Spiegazione. $12+1=13$ e $5^3=125$: a parità di capacità totale gli stati crescono esponenzialmente con il numero di zaini. $39$ somma gli stati invece di moltiplicarli.
La PD per gli zaini multipli esegue $\Theta(m\,n\prod_i(c_i+1))$ passi. Perché è pseudo-polinomiale per un numero $m$ di zaini fissato, ma non quando $m$ fa parte dell'input?
Per $m$ fissato il prodotto è un polinomio di grado $m$ nelle capacità; con $m$ variabile l'esponente cresce con l'istanza
Perché per $m$ fissato il problema è in P
Perché il numero di oggetti non conta
È sempre pseudo-polinomiale
Spiegazione. Con $m$ zaini di capacità $c$ gli stati sono $(c+1)^m$: un polinomio in $c$ solo se $m$ è una costante.
Nella PD per gli zaini multipli (MKP) con $m$ zaini lo stato è $(j,\vet{k})$, con $\vet{k}$ le capacità residue. Quante scelte ha l'oggetto $j$ e quanti passi esegue la PD?
$m$; $\Theta(n\,m^2)$
$2^m$; $\Theta(n\sum_i c_i)$
$m+1$; $\Theta(m\,n\prod_i(c_i+1))$
$2$; $\Theta(nc)$
Spiegazione. L'oggetto resta fuori o va in uno degli $m$ zaini; gli stati sono $n\prod_i(c_i+1)$.
Nel lot sizing senza capacità (ULS) siano $x_t$ la produzione e $s_t$ la scorta alla fine del periodo $t$. Quale enunciato è la proprietà zero-inventory ordering di Wagner e Whitin?
Ogni istanza dell'ULS ha una soluzione ottima con $s_t\,x_t=0$ per ogni periodo $t$
Ogni istanza dell'ULS ha una soluzione ottima con $s_{t-1}\,x_t=0$ per ogni periodo $t$
Ogni soluzione ottima dell'ULS ha $s_{t-1}\,x_t=0$ per ogni periodo $t$
Ogni istanza del CLS ha una soluzione ottima con $s_{t-1}\,x_t=0$ per ogni periodo $t$
Spiegazione. Esiste una soluzione ottima in cui si produce solo quando la scorta entrante è nulla; non tutte le soluzioni ottime la soddisfano, e con le capacità la proprietà può fallire.
Nel lot sizing senza capacità (ULS), la proprietà zero-inventory ordering dice che esiste un piano ottimo che produce solo quando la scorta in ingresso è nulla. Che cosa serve per dimostrarla?
Costi non negativi e produzione senza limiti, per spostare produzione fra due periodi senza aumentare il costo
Costi non negativi e capacità costanti, per spostare produzione fra due periodi senza aumentare il costo
Costi di mantenimento nulli e produzione senza limiti, così le scorte non costano mai nulla
Domande tutte uguali e costi di setup costanti, così i periodi sono intercambiabili
Spiegazione. La dimostrazione sposta produzione da un periodo all'altro senza limiti: con le capacità questo non è sempre possibile, e la proprietà fallisce.
Nel lot sizing senza capacità (ULS) con $m$ periodi, l'algoritmo di Wagner e Whitin usa la ricorrenza $v(t)=\min_j\{v(j-1)+c_{j,t}\}$, con $c_{j,t}$ costo del lotto prodotto in $j$ per i periodi $j,\dots,t$. Quanti passi esegue, se i $c_{j,t}$ si calcolano in modo incrementale?
$\Theta(m^3)$
$\Theta(2^m)$
$\Theta(m\,D_{1,m})$
$\Theta(m^2)$
Spiegazione. La matrice dei costi dei lotti si calcola in $\Theta(m^2)$ e la ricorrenza $v(t)=\min_j\{v(j-1)+c_{j,t}\}$ in $\Theta(m^2)$: è un cammino minimo. Ricalcolare ogni $c_{j,t}$ da zero costerebbe $O(m^3)$.
Lot sizing senza capacità (ULS) su $3$ periodi: domande $d=(10,20,30)$, costo di setup $sc_t=100$, costo variabile nullo, costo $hc_t=1$ per unità di scorta a fine periodo. Il costo del lotto prodotto in $j$ per i periodi $j,\dots,t$ è $c_{j,t}=sc_j+vc_j\,D_{j,t}+\sum_{k=j}^{t-1}hc_k\,D_{k+1,t}$, con $D_{a,b}$ domanda dei periodi da $a$ a $b$. Quanto vale $c_{1,3}$?
$130$
$160$
$180$
$150$
Spiegazione. $c_{1,3}=100+hc_1D_{2,3}+hc_2D_{3,3}=100+50+30=180$: le $20$ unità del periodo $2$ restano in scorta un periodo, le $30$ del periodo $3$ due periodi.
Nel lot sizing senza capacità (ULS), $c_{j,t}$ è il costo del lotto prodotto nel periodo $j$ per coprire le domande dei periodi $j,\dots,t$ (setup $sc_j$, costo variabile $vc_j$, costi di scorta $hc_k$). Come si ottiene $c_{j,t}$ da $c_{j,t-1}$ in tempo costante?
Spiegazione. Estendere il lotto al periodo $t$ aggiunge $d_t$ unità, prodotte in $j$ e tenute in scorta dai periodi $j,\dots,t-1$; il setup è già pagato. Tenendo aggiornata la somma degli $hc_k$, la matrice dei costi si calcola in $\Theta(m^2)$.
Nel lot sizing senza capacità (ULS) con $m$ periodi, la matrice dei costi contiene un valore $c_{j,t}$ per ogni lotto prodotto in $j$ per i periodi $j,\dots,t$, con $1\le j\le t\le m$. Quanti valori contiene con $m=5$?
$15$
$25$
$10$
$32$
Spiegazione. Le coppie $(j,t)$ con $j\le t$ sono $\frac{m(m+1)}{2}=15$. $25$ conta anche le coppie con $j>t$, che non sono lotti; $32=2^5$ conta le scelte dei periodi di setup.
Lot sizing senza capacità (ULS) su $3$ periodi: domande $d=(10,20,30)$, costo di setup $sc_t=100$, costo variabile nullo, costo $hc_t=1$ per unità di scorta a fine periodo. I costi dei lotti sono $c_{1,1}=100$, $c_{1,2}=120$, $c_{1,3}=180$, $c_{2,2}=100$, $c_{2,3}=130$, $c_{3,3}=100$. Con $v(0)=0$ e $v(t)=\min_{1\le j\le t}\{v(j-1)+c_{j,t}\}$, quanto vale $v(3)$?
$220$
$230$
$300$
$180$
Spiegazione. $v(1)=100$, $v(2)=\min\{120,200\}=120$, $v(3)=\min\{180,\ 100+130,\ 120+100\}=180$: un solo lotto nel periodo $1$. Il piano lot-for-lot costa $300$.
Nell'algoritmo di Wagner e Whitin per il lot sizing senza capacità, $v(t)=\min_{1\le j\le t}\{v(j-1)+c_{j,t}\}$ e $j^*(t)$ è il periodo che realizza il minimo. Come si ricostruiscono i periodi dei lotti partendo da $t=m$?
Si registra un lotto in ogni periodo $t$ con $v(t)<v(t-1)$
Si registrano i lotti in $j^*(1),j^*(2),\dots,j^*(m)$, in avanti
Si registra un lotto in $j^*(t)$ e si pone $t\leftarrow j^*(t)-1$, fino a $t=0$
Si registra un lotto in $j^*(t)$ e si pone $t\leftarrow t-1$
Spiegazione. L'ultimo lotto è prodotto in $j^*(m)$ e copre i periodi da $j^*(m)$ a $m$; il resto del piano è la soluzione ottima dei periodi $1,\dots,j^*(m)-1$.
Nell'algoritmo di Wagner e Whitin per il lot sizing senza capacità, $v(t)$ è il costo ottimo dei periodi $1,\dots,t$ con scorta nulla alla fine di $t$. Che cosa rappresenta l'indice $j$ nella ricorrenza $v(t)=\min_{1\le j\le t}\{v(j-1)+c_{j,t}\}$?
La quantità prodotta nel periodo $t$
Il periodo dell'ultimo lotto, che produce le domande dei periodi $j,\dots,t$
Il periodo del primo lotto, che produce le domande dei periodi $1,\dots,j$
Il numero di lotti del piano
Spiegazione. Per la proprietà zero-inventory ordering, la scorta è nulla alla fine di $j-1$, e il sottoproblema residuo è l'istanza con periodi $1,\dots,j-1$. I sottoproblemi generati sono quindi $t$.
Nel lot sizing senza capacità (ULS) con $m$ periodi, una soluzione con la proprietà zero-inventory ordering produce solo con scorta in ingresso nulla, e quindi è decisa dai periodi in cui si produce (il periodo $1$ produce sempre se $d_1>0$). Quante sono queste soluzioni con $m=6$?
$32$
$64$
$21$
$720$
Spiegazione. Ogni periodo $t\in\{2,\dots,6\}$ produce o no in modo indipendente: $2^{m-1}=32$. Il periodo $1$ deve produrre, perché la scorta iniziale è nulla.
Nel lot sizing senza capacità (ULS), in una soluzione ottima con la proprietà zero-inventory ordering ($s_{t-1}x_t=0$ per ogni $t$), quanto produce un periodo $j$ con produzione positiva?
Esattamente la domanda $d_j$ del proprio periodo
La domanda totale $D_{1,m}$ di tutti i periodi
Una quantità qualsiasi, purché la scorta resti non negativa
Esattamente le domande dei periodi $j,\dots,t$, dove $t+1$ è il periodo di produzione successivo (o $t=m$)
Spiegazione. Con scorta in ingresso nulla, il periodo $j$ deve coprire tutta la domanda fino al prossimo periodo di produzione, che a sua volta parte con scorta nulla: i lotti coprono blocchi di periodi consecutivi.
Nel lot sizing senza capacità (ULS) $D_{j,t}=\sum_{k=j}^td_k$ è la domanda dei periodi da $j$ a $t$. Con domande $d=(20,10,30,40,10)$, quanto vale $D_{2,4}$?
$40$
$110$
$80$
$70$
Spiegazione. $D_{2,4}=d_2+d_3+d_4=10+30+40=80$. $70$ dimentica $d_2$; $110$ è la domanda totale.
Nel lot sizing senza capacità una soluzione ammissibile è un vettore di produzioni $(x_1,\dots,x_m)$ con scorte $s_t=\sum_{j\le t}x_j-D_{1,t}\ge0$ per ogni $t$ e $s_m=0$. Con $d=(20,10,30,40,10)$, quale piano è ammissibile?
$(30,0,70,0,20)$
$(30,0,70,0,10)$
$(10,20,30,40,10)$
$(30,0,30,30,20)$
Spiegazione. Scorte di $(30,0,70,0,10)$: $10,0,40,0,0$. $(10,20,\dots)$ ha $s_1=-10$; $(30,0,30,30,20)$ ha $s_4=-10$; $(30,0,70,0,20)$ finisce con scorta $10$.
Nel lot sizing senza capacità il costo del lotto prodotto nel periodo $j$ per i periodi $j,\dots,t$ è $c_{j,t}=sc_j+vc_jD_{j,t}+\sum_{k=j}^{t-1}hc_kD_{k+1,t}$. Con $d=(20,10,30,40,10)$, $sc_t=50$, $vc_t=0$ e $hc_t=1$, quanto vale $c_{1,3}$?
$120$
$110$
$90$
$160$
Spiegazione. $50+hc_1D_{2,3}+hc_2D_{3,3}=50+40+30=120$: la domanda del periodo $3$ resta a scorta due periodi, quella del periodo $2$ uno. $90$ conta la scorta una volta sola.
Nel costo di un lotto del lot sizing senza capacità, $c_{j,t}=sc_j+vc_jD_{j,t}+\sum_{k=j}^{t-1}hc_kD_{k+1,t}$, perché il termine di mantenimento del periodo $k$ è $hc_kD_{k+1,t}$?
Perché ogni unità resta a scorta un solo periodo
Perché si tiene a scorta la domanda dei periodi da $j$ a $k$
Perché il costo di mantenimento si paga solo nel periodo del setup
Alla fine del periodo $k$ restano a scorta esattamente le unità destinate ai periodi $k+1,\dots,t$
Spiegazione. Il lotto copre $D_{j,t}$; dopo il periodo $k$ sono già state consegnate le domande fino a $k$, quindi in magazzino c'è $D_{k+1,t}$, che paga $hc_k$ per unità.
L'algoritmo di Wagner e Whitin per il lot sizing senza capacità con $m$ periodi calcola $v(t)=\min_{1\le j\le t}\{v(j-1)+c_{j,t}\}$ per $t=1,\dots,m$. Quanti passi esegue?
$\Theta(m)$: un termine per periodo
$\Theta(m\,D_{1,m})$: pseudo-polinomiale nella domanda
$\Theta(m^2)$: una coppia $(j,t)$ con $j\le t$ per ogni termine del minimo
$\Theta(2^m)$: un termine per ogni insieme di periodi di setup
Spiegazione. Le coppie $(j,t)$ sono $m(m+1)/2$, e lo stesso ordine vale per il calcolo della matrice dei costi $c_{j,t}$. Per questo l'ULS è polinomiale, a differenza del CLS.
Nel modello del lot sizing senza capacità ($x_t$ produzione, $s_t$ scorta, $y_t$ setup del periodo $t$), quale vincolo impone un setup in ogni periodo con produzione positiva?
$x_t\le D_{t,m}\,y_t$, con $D_{t,m}$ la domanda dei periodi da $t$ a $m$
$s_{t-1}+x_t=d_t+s_t$
$y_t\le x_t$
$x_t\le d_t$
Spiegazione. Se $y_t=0$ il vincolo forza $x_t=0$; con $y_t=1$ si può produrre fino alla domanda residua, che è il big-$M$ naturale senza capacità.
Lot sizing senza capacità con domande $d=(20,10,30,40,10)$, $sc_t=50$, $vc_t=0$, $hc_t=1$. Quanto costa il piano lotto per lotto, che produce in ogni periodo la sua domanda?
$110$
$50$
$360$
$250$
Spiegazione. Cinque setup da $50$ e nessuna scorta: $250$. Produrre tutto nel periodo $1$ costerebbe $50$ di setup più $90+80+50+10=230$ di scorta.
Lot sizing senza capacità con domande $d=(20,10,30,40,10)$: il piano $(x_1,\dots,x_5)=(60,0,0,50,0)$ è ammissibile? Quali sono le scorte $s_t=\sum_{j\le t}x_j-D_{1,t}$?
Sì: $(40,30,0,50,0)$
No: $s_3<0$
Sì: $(40,30,0,10,0)$
No: la scorta finale è positiva
Spiegazione. $60-20=40$, $40-10=30$, $30-30=0$, $0+50-40=10$, $10-10=0$: tutte non negative e finale nulla.
Nel lot sizing senza capacità con $m=5$ periodi, quanti piani rispettano la proprietà zero-inventory (si produce solo con scorta vuota), se ogni piano è individuato dai suoi periodi di setup e il periodo $1$ ha sempre un setup?
$120$
$16$
$32$
$5$
Spiegazione. Il periodo $1$ deve produrre; ognuno degli altri $4$ periodi produce o no: $2^4=16$. Ogni piano produce, in un periodo di setup, la domanda fino al setup successivo.
Nel lot sizing senza capacità con $d=(20,10,30,40,10)$, $sc_t=50$, $vc_t=0$ e $hc_t=1$, il costo del lotto prodotto nel periodo $j$ per i periodi $j,\dots,t$ è $c_{j,t}=sc_j+\sum_{k=j}^{t-1}hc_kD_{k+1,t}$. Quanto vale $c_{3,4}$?
$90$
$70$
$120$
$50$
Spiegazione. $50+hc_3D_{4,4}=50+40=90$: la domanda del periodo $4$ resta a scorta un periodo.
La matrice dei costi dell'algoritmo di Wagner e Whitin contiene un valore $c_{j,t}$ per ogni coppia di periodi $j\le t$. Quanti valori ha con $m=5$ periodi?
$10$
$32$
$15$
$25$
Spiegazione. Le coppie con $j\le t$ sono $m(m+1)/2=15$; calcolandole per $t$ crescente ogni valore si ottiene dal precedente in tempo costante.
Nella PD di Wagner e Whitin $v(t)=\min_{j\le t}\{v(j-1)+c_{j,t}\}$ per il lot sizing senza capacità con $m$ periodi: quanti passi servono, e che cosa calcola la ricorrenza?
$\Theta(m)$; un albero ricoprente minimo
$\Theta(2^m)$; tutti i piani di produzione
$\Theta(m^3)$; un flusso massimo
$\Theta(m^2)$; un cammino minimo nella rete dei lotti
Spiegazione. I nodi sono $0,\dots,m$ e l'arco $(j-1,t)$ costa $c_{j,t}$: $v(t)$ è la lunghezza di un cammino minimo da $0$ a $t$.
Nel lot sizing con capacità (CLS) su $m$ periodi, con scorta iniziale e finale nulle e $D_{t+1,m}$ domanda dei periodi da $t+1$ a $m$, qual è lo stato della PD e dove si legge il valore ottimo?
Il periodo $t$ dell'ultimo lotto prodotto, come nell'ULS; il valore ottimo è $v(m)$
La coppia $(t,x)$ del periodo e della produzione, con $x\le cap_t$; il valore ottimo è $v(m,cap_m)$
La coppia $(t,k)$ del periodo e della scorta finale, con $k\le D_{t+1,m}$; il valore ottimo è $v(m,0)$
La coppia $(t,k)$ del periodo e del numero di setup, con $k\le t$; il valore ottimo è $\min_k v(m,k)$
Spiegazione. Con le capacità la proprietà zero-inventory ordering non vale, quindi lo stato deve contenere la scorta; alla fine dell'orizzonte la scorta è nulla.
Nella PD del lot sizing con capacità (CLS), $v(t,k)$ è il costo minimo dei periodi $1,\dots,t$ che termina con scorta $k$; la scorta iniziale è nulla. Quanto vale $v(0,k)$ per $k>0$?
$k$: una unità di costo per ogni unità di scorta
$+\infty$: questi stati non sono raggiungibili
$0$: nessun costo è ancora stato pagato
$-\infty$: questi stati non sono raggiungibili
Spiegazione. Il valore $+\infty$ segna gli stati che non si possono raggiungere; solo $v(0,0)=0$.
Nel lot sizing con capacità (CLS) su $m$ periodi, con domanda totale $D$ e capacità massima $C$, quale affermazione sulla complessità è corretta?
La PD esegue $O(mDC)$ passi; con capacità costante è polinomiale, con capacità generali NP-difficile
La PD esegue $O(mDC)$ passi; con capacità costante è NP-difficile in senso forte
La PD di Wagner e Whitin sui lotti risolve anche il CLS in $\Theta(m^2)$ passi
La PD esegue $O(m^2)$ passi; il CLS è polinomiale per qualsiasi capacità
Spiegazione. Con le capacità serve la scorta nello stato, e il numero di stati dipende dalla domanda totale $D$; con capacità costante vale una proprietà più debole che rende il problema polinomiale.
Nella PD del lot sizing con capacità (CLS), lo stato $(t,k)$ è il periodo $t$ con scorta finale $k$, e si considerano solo $k\le D_{t+1,m}$ (domanda dei periodi da $t+1$ a $m$). Perché?
Perché gli stati con scorta maggiore hanno costo nullo
Una scorta maggiore della domanda residua resterebbe inutilizzata e violerebbe la scorta finale nulla
Perché la capacità del periodo $t$ è al più $D_{t+1,m}$
Perché la scorta non può superare la domanda del periodo $t$
Spiegazione. La scorta alla fine di $t$ serve solo ai periodi successivi e alla fine deve essere nulla: oltre $D_{t+1,m}$ non può essere consumata, quindi quegli stati non portano a soluzioni ammissibili.
Lot sizing con capacità (CLS) su $2$ periodi: domande $d=(2,3)$, capacità $cap_t=4$, setup $sc_t=10$, costo variabile nullo, costo di scorta $hc_1=1$ per unità a fine periodo $1$; scorte iniziale e finale nulle. Quanto vale il costo ottimo?
$20$
$22$
$12$
$10$
Spiegazione. Il piano $(2,3)$ costa $20$; $(4,1)$ costa $10+2+10=22$; un solo setup ($5$ unità nel periodo $1$) supera la capacità $4$, quindi $12$ non è ammissibile.
Nella PD del lot sizing con capacità, lo stato $(t,k)$ ha scorta $k$ alla fine del periodo $t$. Da quali stati $(t-1,k')$ si arriva a $(t,k)$?
Da tutti gli stati $(t-1,k')$ con $k'\le k$
Solo dallo stato $(t-1,0)$, per la proprietà zero-inventory
Da quelli con $k'=k+d_t$
Da quelli per cui la produzione $x=k+d_t-k'$ soddisfa $0\le x\le cap_t$
Spiegazione. Il bilancio $k'+x=d_t+k$ fissa la produzione del periodo $t$, che deve essere non negativa e rispettare la capacità. Con le capacità la proprietà zero-inventory non vale più.
Nella PD del lot sizing con capacità su $m$ periodi, con domanda totale $D$ e capacità massima $C$, perché il numero di passi è $O(mDC)$?
Ci sono $2^m$ scelte di setup, ciascuna valutata in $O(DC)$
Ci sono $D\cdot C$ stati e $m$ transizioni per stato
Ci sono al più $m(D+1)$ stati $(t,k)$, e ognuno ha al più $C+1$ transizioni, una per produzione
Ci sono $m$ stati, e ognuno richiede $DC$ confronti
Spiegazione. La scorta finale di un periodo va da $0$ a $D$, e la produzione del periodo da $0$ a $C$. Il tempo è pseudo-polinomiale: contiene i numeri $D$ e $C$.
Perché l'algoritmo di Wagner e Whitin, che sceglie solo i periodi dei lotti, non risolve il lot sizing con capacità (CLS)?
Perché il CLS ha scorta finale libera
Con le capacità può non esistere un piano ottimo con produzione solo a scorta in ingresso nulla
Perché nel CLS i costi di setup sono nulli
Perché nel CLS le domande possono essere negative
Spiegazione. Se la domanda di un periodo supera la sua capacità, un periodo precedente deve produrre in anticipo anche se ha già scorta: la proprietà zero-inventory ordering non vale, e servono gli stati con la scorta.
Nella PD del lot sizing con capacità, la transizione da $(t-1,k')$ a $(t,k)$ produce $x=k+d_t-k'$ unità nel periodo $t$. Quali costi si aggiungono?
$sc_t$ se $x>0$, più $vc_t\,x$, più $hc_t\,k$ per la scorta finale del periodo $t$
Sempre $sc_t$, più $vc_t\,x$
$sc_t$ se $x>0$, più $hc_t\,k'$ per la scorta iniziale
Solo $hc_t\,k$, perché il setup si paga una volta
Spiegazione. Il setup si paga solo se si produce; la scorta che resta alla fine del periodo paga $hc_t$ per unità, come nella funzione obiettivo del modello.
Lot sizing con capacità su $2$ periodi con domande $d=(5,1)$, capacità $cap_t=4$ e scorta iniziale nulla. Che cosa dà la PD sugli stati $(1,k)$, scorta $k$ alla fine del periodo $1$?
$v(1,k)=0$ per ogni $k$, perché il periodo $1$ non produce
$v(1,1)=sc_1+hc_1$, con una unità in scorta
$v(1,k)=+\infty$ per ogni $k$: la domanda del periodo $1$ supera la sua capacità
$v(1,0)=sc_1$, gli altri $+\infty$
Spiegazione. Senza scorta iniziale il periodo $1$ deve produrre almeno $5$ unità, ma la capacità è $4$: nessuno stato del periodo $1$ è raggiungibile, e l'istanza non ha soluzioni.
Il lot sizing con capacità (CLS) è NP-difficile in generale, e la sua PD è pseudo-polinomiale. Che cosa succede quando la capacità è la stessa in tutti i periodi?
Basta l'algoritmo di Wagner e Whitin senza modifiche
Il problema si risolve in tempo polinomiale
Il problema resta NP-difficile in senso forte
La PD diventa esponenziale in $m$
Spiegazione. Con capacità costante esistono algoritmi polinomiali; con capacità generali il CLS è NP-difficile. In entrambi i casi la proprietà zero-inventory ordering può non valere.
Lot sizing capacitato con domande $d=(2,1,3,4,1)$ e capacità $cap_t=4$. Il piano $(3,0,4,4,0)$ è ammissibile; quali sono le scorte $s_t=\sum_{j\le t}x_j-D_{1,t}$ alla fine dei periodi?
$(1,0,0,1,0)$
$(1,0,1,1,0)$
$(1,1,1,1,0)$
$(3,0,4,4,0)$
Spiegazione. $3-2=1$, $1-1=0$, $0+4-3=1$, $1+4-4=1$, $1+0-1=0$. Il periodo $4$ produce mentre c'è scorta: con capacità la proprietà zero-inventory non vale.
La PD per il lot sizing capacitato usa lo stato $(t,k)$: $v(t,k)$ è il costo ottimo dei periodi $1,\dots,t$ con scorta $k$ alla fine del periodo $t$. Perché basta considerare $k\le D_{t+1,m}$?
La scorta deve essere vuota alla fine dell'orizzonte, quindi non supera mai la domanda dei periodi successivi
Perché la capacità è al più $D_{t+1,m}$
Perché la scorta è sempre nulla
Perché $k$ deve essere un multiplo della capacità
Spiegazione. Unità in più di $D_{t+1,m}$ non potrebbero mai essere consegnate prima della fine: un piano con scorta finale vuota non le produce.
Nella PD per il lot sizing capacitato, $v(t,k)=\min\{v(t-1,k+d_t-x)+f_t(x):x\in X_t(k)\}+hc_tk$, dove $x$ è la produzione del periodo $t$. Perché lo stato del periodo precedente è $k+d_t-x$?
Perché si produce sempre $d_t$
Perché la scorta del periodo precedente è sempre $k$
Perché la domanda si paga nel periodo successivo
Scorta iniziale del periodo $t$ più produzione meno domanda deve dare la scorta finale $k$
Spiegazione. Dal bilanciamento $s_{t-1}+x=d_t+k$ si ricava $s_{t-1}=k+d_t-x$. Le produzioni ammesse sono $X_t(k)=\{0,\dots,\min\{cap_t,k+d_t\}\}$.
La PD per il lot sizing capacitato esegue $O(m\,D\,C)$ passi, con $m$ periodi, $D$ domanda totale e $C$ capacità massima. Come si classifica l'algoritmo?
Esponenziale in $m$
Lineare nella dimensione dell'istanza
Pseudo-polinomiale: è polinomiale nei valori numerici $D$ e $C$, non nella loro lunghezza in bit
Polinomiale nella dimensione dell'istanza
Spiegazione. Il CLS con capacità generali è NP-difficile, quindi non ci si aspetta un algoritmo polinomiale; la PD è esatta e veloce quando $D$ e $C$ sono piccoli.
Il lot sizing capacitato è NP-difficile con capacità generali, ma diventa polinomiale con capacità costante $cap_t=C$. Quale proprietà dei piani ottimi prende il posto della proprietà zero-inventory ordering?
Ogni periodo produce esattamente la propria domanda
Fra due periodi consecutivi con scorta vuota al più un periodo produce una quantità strettamente fra $0$ e $C$; gli altri producono $0$ o $C$
Si produce solo con scorta vuota
Ogni periodo produce esattamente $C$
Spiegazione. Con capacità costante i periodi «pieni» e «vuoti» si possono scambiare senza perdere ammissibilità, e resta un solo periodo frazionario per blocco. Con capacità diverse la proprietà cade.
La PD di Wagner e Whitin per il lot sizing senza capacità enumera i lotti (periodi da $j$ a $t$ coperti da una sola produzione). Perché non si può usare per il lot sizing capacitato?
Si basa sulla proprietà zero-inventory, che con le capacità non vale: un lotto può non entrare nella capacità del suo periodo
Perché con le capacità i costi di setup sono nulli
Perché il CLS ha un solo periodo
Si può usare senza modifiche
Spiegazione. Nel piano ottimo $(3,0,4,4,0)$ con $cap_t=4$ il periodo $4$ produce con scorta positiva; per questo la PD del CLS usa lo stato (periodo, scorta).
Nella PD per il lot sizing capacitato lo stato $(t,k)$ ha $k\in\{0,\dots,D_{t+1,m}\}$. Con domande $d=(2,1,3,4,1)$, quanti stati ci sono per $t=1,\dots,5$ in tutto?
Nella PD per il lot sizing capacitato ogni stato $(t,k)$ prova le produzioni $x\in\{0,\dots,\min\{cap_t,k+d_t\}\}$. Da dove viene il bound $O(m\,D\,C)$, con $D$ domanda totale e $C$ capacità massima?
Da $m^2$ coppie di periodi
Da $D\cdot C$ coppie di periodi
Al più $D+1$ scorte per ciascuno degli $m$ periodi, e al più $C+1$ produzioni per stato
Da $2^m$ piani di setup
Spiegazione. Stati $O(mD)$ per tentativi $O(C)$: pseudo-polinomiale nei valori $D$ e $C$.
Lot sizing capacitato con capacità costante $C=4$ e domande $d=(2,1,3,4,1)$: il piano ottimo $(3,0,4,4,0)$ ha scorte $(1,0,1,1,0)$. Come rispetta la proprietà dei piani a capacità costante?
Ogni periodo produce la propria domanda
Fra due periodi con scorta vuota, nei periodi $1$–$2$ solo il periodo $1$ produce fra $0$ e $4$, e nei periodi $3$–$5$ si produce $0$ o $4$
Ogni periodo produce esattamente $4$
Si produce solo con scorta vuota
Spiegazione. La proprietà permette al più una produzione «frazionaria» fra due istanti di scorta vuota: è ciò che rende polinomiale il caso a capacità costante.
Che cosa si sa della complessità del lot sizing capacitato a un prodotto?
È sempre polinomiale
È NP-difficile anche senza capacità
Con capacità costante è NP-difficile
Con capacità costante è polinomiale; con capacità generali è NP-difficile
Spiegazione. Con capacità costante vale una proprietà più debole e il problema è polinomiale; in generale la PD sugli stati $(t,k)$ è solo pseudo-polinomiale.
Cambio monete (CCP): con i tagli $w=(3,5)$ si deve dare un resto di esattamente $c=7$ con il minimo numero di monete. Quanto vale $v(7)$ con la ricorrenza $v(k)=\min_{j:\,w_j\le k}\{1+v(k-w_j)\}$, $v(0)=0$ e minimo su un insieme vuoto uguale a $+\infty$?
$+\infty$
$0$
$2$
$3$
Spiegazione. $v(1)=v(2)=+\infty$, $v(4)=1+v(1)=+\infty$, quindi $v(7)=\min\{1+v(4),1+v(2)\}=+\infty$: il resto $7$ non si può dare. Con il valore $0$ l'algoritmo direbbe che non serve alcuna moneta.
Nel cambio monete (CCP) i tagli hanno valori $w_j$ e il resto è $c$; nello zaino illimitato (UKP) i tipi hanno pesi $w_j$, profitti $p_j$ e la capacità è $c$; in entrambi le copie sono illimitate. Che differenza c'è?
Il CCP chiede somma al più $c$ e minimizza le monete; l'UKP chiede peso esattamente $c$ e massimizza il profitto
Il CCP chiede somma esattamente $c$ e massimizza le monete; l'UKP chiede peso al più $c$ e minimizza il peso
Il CCP ammette al più una moneta per taglio; l'UKP ammette copie illimitate di ogni tipo
Il CCP chiede somma esattamente $c$ e minimizza le monete; l'UKP chiede peso al più $c$ e massimizza il profitto
Spiegazione. Le due ricorrenze si somigliano, ma il CCP richiede l'uguaglianza (da qui $+\infty$ per i resti impossibili) e ha un obiettivo di minimo.
Nel cambio monete (CCP) con $n$ tagli e resto $c$, la PD calcola $v(k)$, il minimo numero di monete per il resto $k$, per $k=0,\dots,c$. Quanti passi esegue?
$\Theta(n^c)$
$\Theta(c\log n)$, polinomiale
$\Theta(nc)$, pseudo-polinomiale
$\Theta(n+c)$
Spiegazione. Per ciascuno dei $c+1$ valori $k$ si provano gli $n$ tagli: $\Theta(nc)$, polinomiale nel valore di $c$ e non nella sua dimensione.
Cambio monete (CCP) con tagli $w=(1,3,4)$ e resto $c=6$. Il taglio $j$ si usa al più $\lfloor c/w_j\rfloor$ volte. Quanti vettori $(x_1,x_2,x_3)$ con $0\le x_j\le\lfloor c/w_j\rfloor$ ci sono, prima di controllare la somma?
$12$
$27$
$64$
$42$
Spiegazione. $(6+1)(2+1)(1+1)=7\cdot3\cdot2=42$; solo quelli con somma esattamente $6$ sono ammissibili.
Nella PD per il cambio monete, $v(k)$ è il minimo numero di monete per il resto $k$. Quale valore si assegna a $v(k)$ quando nessun taglio $w_j\le k$ dà un resto $k-w_j$ ottenibile?
$k$: si usano monete da $1$
$+\infty$: il resto $k$ non si può dare
$0$: non serve nessuna moneta
$-\infty$: il sottoproblema è inammissibile
Spiegazione. In un problema di minimo un sottoproblema senza soluzioni vale $+\infty$, così non viene mai scelto dal minimo. $v(0)=0$ è il solo caso con zero monete.
Nella PD per il cambio monete, $s(k)$ è il taglio che realizza il minimo in $v(k)=\min_{j:\,w_j\le k}\{1+v(k-w_j)\}$. Come si ricostruiscono le monete di una soluzione ottima per il resto $c$?
Partendo da $k=c$: si prende una moneta $w_{s(k)}$ e si pone $k\leftarrow k-w_{s(k)}$, fino a $k=0$
Si prendono $v(c)$ monete del taglio $s(c)$
Partendo da $k=0$: si prende $w_{s(k)}$ e si pone $k\leftarrow k+w_{s(k)}$
Si prendono le monete in ordine di taglio decrescente, come il greedy
Spiegazione. Ogni passo della ricorrenza toglie una moneta dal resto; i tagli si leggono a ritroso dallo stato finale $c$ e possono ripetersi.
Nell'albero di ricorsione della PD per il cambio monete, ogni nodo è una chiamata $v(k)$. Quanti figli ha il nodo $v(k)$?
Due: usare o non usare il taglio $1$
$k$, uno per ogni resto minore
Uno solo, con il taglio più grande che entra
Uno per ogni taglio $w_j\le k$, con la chiamata $v(k-w_j)$
Spiegazione. La ricorrenza prova come prima moneta ogni taglio che entra nel resto, e ogni scelta lascia il sottoproblema $v(k-w_j)$. Lo stesso resto ricompare in rami diversi: sottoproblemi sovrapposti.
Cambio monete (CCP) con tagli $w=(2,5)$. Con $v(0)=0$, $v(k)=\min_{j:\,w_j\le k}\{1+v(k-w_j)\}$ e $v(k)=+\infty$ per i resti non ottenibili, quanto vale $v(8)$?
$2$
$3$
$4$
$+\infty$
Spiegazione. $v=(0,+\infty,1,+\infty,2,1,3,2,4)$ per $k=0,\dots,8$: $8=2+2+2+2$, mentre $8-5=3$ non è ottenibile. Il greedy partirebbe da $5$ e resterebbe bloccato.
La PD del cambio monete, $v(k)=\min_{j:\,w_j\le k}\{1+v(k-w_j)\}$, assomiglia alla prima PD dello zaino illimitato, $v(k)=\max_{j:\,w_j\le k}\{p_j+v(k-w_j)\}$. Quali sono le due differenze?
Nessuna: con $p_j=1$ le due ricorrenze coincidono
Minimo invece di massimo, e $+\infty$ per i resti non ottenibili perché la somma deve essere esatta
Copie limitate invece che illimitate, e tabella bidimensionale
Massimo invece di minimo, e $0$ per i resti non ottenibili
Spiegazione. Il CCP minimizza il numero di monete e richiede somma esattamente $c$; lo zaino massimizza il profitto e accetta capacità non usata, quindi i suoi sottoproblemi valgono almeno $0$.
Nel cambio monete (CCP: tagli $w_1,\dots,w_n$, resto $c$, si minimizza il numero di monete) una soluzione è un vettore $(x_1,\dots,x_n)$ di monete per taglio. Quale condizione la rende ammissibile?
$\sum_jw_jx_j\ge c$
$\sum_jw_jx_j=c$ con $x_j\in\Z_{\ge0}$
$\sum_jw_jx_j\le c$ con $x_j\in\{0,1\}$
$\sum_jx_j=c$
Spiegazione. Il resto va dato esattamente; ogni taglio si può usare più volte, con $x_j\le\lfloor c/w_j\rfloor$. Con $\le$ il problema ammetterebbe di non dare il resto.
La PD per il cambio monete calcola il minimo numero di monete per ogni resto $0,1,\dots,c$, provando gli $n$ tagli per ciascuno. Quanti passi esegue e perché non è polinomiale?
$\Theta(nc)$, pseudo-polinomiale: dipende dal valore $c$, non dalla sua lunghezza in bit
$\Theta(n\log c)$, polinomiale
$\Theta(2^n)$, esponenziale nel numero di tagli
$\Theta(c^2)$, quadratico nel resto
Spiegazione. Ci sono $c+1$ resti e per ciascuno si provano $n$ tagli. Raddoppiare $c$ raddoppia i passi, ma aggiunge un solo bit all'istanza.
Cambio monete con tagli $w=(1,3,4)$ e resto $c=6$: si minimizza il numero di monete. Quale vettore $(x_1,x_2,x_3)$ è ottimo, e quante monete usa la scelta greedy «prima il taglio più grande»?
$(6,0,0)$ con $6$ monete; il greedy ne usa $3$
$(0,2,0)$ con $2$ monete; il greedy ne usa $3$ ($4+1+1$)
$(2,0,1)$ con $3$ monete; il greedy ne usa $3$
$(0,2,0)$ con $2$ monete; il greedy ne usa $2$
Spiegazione. $3+3=6$ con due monete. Il greedy prende $4$ e poi due monete da $1$: con questi tagli non è ottimo, da cui la PD.
Nel cambio monete con tagli $w=(1,3,4)$ e resto $c=6$, ogni componente di una soluzione ammissibile soddisfa $x_j\le\lfloor c/w_j\rfloor$. Quali sono i limiti?
$x_1\le6$, $x_2\le2$, $x_3\le1$
$x_j\le1$ per ogni $j$
$x_1\le6$, $x_2\le3$, $x_3\le2$
$x_1+x_2+x_3\le6$, nient'altro
Spiegazione. $\lfloor6/1\rfloor=6$, $\lfloor6/3\rfloor=2$, $\lfloor6/4\rfloor=1$: le soluzioni sono finite, ma il loro numero cresce rapidamente con $c$ e $n$.
Nel cambio monete (CCP) con tagli $w_1,\dots,w_n$ e importo $c$: che cosa calcola $v(k)=\min_{j:\,w_j\le k}\{1+v(k-w_j)\}$ con $v(0)=0$, e in quanti passi?
Il minimo numero di monete; $\Theta(c\log c)$
Il massimo valore con $k$ monete; $\Theta(n^2)$
Il minimo numero di monete per l'importo $k$; $\Theta(nc)$
Il numero di modi di formare $k$; $\Theta(nc)$
Spiegazione. Si prova ogni taglio per la prima moneta; per ognuno dei $c+1$ importi si guardano $n$ tagli.
Nel taglio delle aste (RCP) un'asta di lunghezza intera $n$ si taglia nelle posizioni intere e i pezzi si vendono a prezzi dati. Quanti sono gli schemi di taglio di un'asta di lunghezza $n=5$?
$5$
$16$
$32$
$7$
Spiegazione. Ognuna delle $n-1=4$ posizioni interne si taglia o no: $2^{n-1}=16$ schemi. Gli schemi sono più dei vettori soluzione, perché schemi diversi possono dare gli stessi pezzi.
Nel taglio delle aste (RCP) un'asta di lunghezza $n$ si taglia in pezzi interi e il pezzo di lunghezza $j$ vale $p_j$ (l'istanza elenca $p_1,\dots,p_n$). La PD $v(\ell)=\max_{j\le\ell}\{p_j+v(\ell-j)\}$ esegue $\Theta(n^2)$ passi. Perché è un tempo polinomiale, mentre il $\Theta(nc)$ della PD del KP non lo è?
L'input contiene gli $n$ prezzi, quindi $n$ cresce con la dimensione dell'istanza
I prezzi $p_j$ sono interi, quindi la tabella ha valori interi
La lunghezza $n$ è scritta in binario con $\log n$ cifre
Non lo è: anche $\Theta(n^2)$ è un tempo pseudo-polinomiale
Spiegazione. Nel KP la capacità $c$ è un numero scritto con $\log c$ cifre; nel taglio delle aste l'istanza elenca $n$ profitti, quindi $n$ è già una misura della dimensione.
Nel taglio delle aste (RCP), $v(\ell)$ è il massimo ricavo da un'asta di lunghezza $\ell$, con il pezzo di lunghezza $j$ venduto a $p_j$, e $v(\ell)=\max_{j\le\ell}\{p_j+v(\ell-j)\}$. A che cosa serve il caso base $v(0)=0$?
A vietare l'asta senza tagli, che non è uno schema ammissibile
A garantire che l'asta venga tagliata almeno una volta
A nulla: la ricorrenza non legge mai la cella $v(0)$
Al termine $p_\ell+v(0)$, cioè vendere l'asta intera senza tagli
Spiegazione. Il termine $p_\ell+v(0)$ corrisponde a vendere l'asta intera senza tagli; senza il caso base la ricorsione non terminerebbe.
Nel taglio delle aste (RCP) la ricorrenza è $v(0)=0$ e $v(\ell)=\max_{1\le j\le\ell}\{p_j+v(\ell-j)\}$. Senza lookup table, la ricorsione top-down per $v(\ell)$ fa una chiamata per ogni $v(\ell-j)$, $j=1,\dots,\ell$. Quante chiamate in tutto, contando la prima, servono per $v(4)$?
$16$
$5$
$10$
$24$
Spiegazione. Detto $C(\ell)$ il numero di chiamate, $C(0)=1$ e $C(\ell)=1+\sum_{i<\ell}C(i)$: $C=1,2,4,8,16$, cioè $2^\ell$. Con la lookup table bastano $5$ valori, $v(0),\dots,v(4)$.
Taglio delle aste (RCP): asta di lunghezza $4$, prezzi dei pezzi $p=(1,5,8,9)$ per le lunghezze $1,2,3,4$. Con $v(0)=0$ e $v(\ell)=\max_{1\le j\le\ell}\{p_j+v(\ell-j)\}$, quanto vale $v(4)$?
$9$
$11$
$20$
$10$
Spiegazione. $v(1)=1$, $v(2)=5$, $v(3)=8$, $v(4)=\max\{1+8,5+5,8+1,9+0\}=10$: due pezzi di lunghezza $2$. Vendere l'asta intera dà solo $9$.
Nella prima PD per il taglio delle aste, $s(\ell)$ è la lunghezza del primo pezzo che realizza il massimo in $v(\ell)$. Come si ricostruiscono i pezzi di un taglio ottimo dell'asta di lunghezza $n$?
Partendo da $\ell=1$ e aggiungendo pezzi finché la somma è $n$
Si legge $v(n)$ e si divide per il prezzo massimo
Partendo da $\ell=n$: si taglia un pezzo $s(\ell)$ e si pone $\ell\leftarrow\ell-s(\ell)$, fino a $\ell=0$
Si tagliano $n/s(n)$ pezzi di lunghezza $s(n)$
Spiegazione. Ogni passo toglie il primo pezzo scelto dalla ricorrenza e passa all'asta residua; le lunghezze si leggono a ritroso e possono ripetersi.
Nella seconda PD per il taglio delle aste, $v(j,\ell)$ è il massimo ricavo da un'asta di lunghezza $\ell$ usando pezzi di lunghezza al più $j$. Perché il caso base è $v(0,\ell)=-\infty$ per $\ell>0$?
Perché la tabella parte da $\ell=1$
Senza lunghezze di pezzo disponibili un'asta di lunghezza positiva non si può dividere: nessuna soluzione
Perché i prezzi possono essere negativi
Perché l'asta intera non si può vendere senza tagli
Spiegazione. L'asta va divisa per intero in pezzi; con $j=0$ non c'è nessun pezzo, e $-\infty$ esclude il caso dal massimo. Vale invece $v(j,0)=0$.
Nella seconda PD per il taglio delle aste, $v(j,\ell)=\max\{v(j-1,\ell),\ p_j+v(j,\ell-j)\}$ per $j\le\ell$. Che cosa rappresenta il termine $p_j+v(j,\ell-j)$?
Tagliare un pezzo di lunghezza $j$, potendo tagliarne altri della stessa lunghezza
Non usare pezzi di lunghezza $j$
Tagliare un pezzo di lunghezza $j$ e passare alle lunghezze minori
Vendere l'asta intera di lunghezza $\ell$
Spiegazione. Il termine resta nella riga $j$, quindi la lunghezza $j$ si può usare ancora; $v(j-1,\ell)$ esclude invece la lunghezza $j$. È la stessa struttura dello zaino illimitato.
Taglio delle aste con prezzi $p=(1,5,8,9)$ per le lunghezze $1,2,3,4$. Nella seconda PD, $v(j,\ell)$ è il massimo ricavo da un'asta di lunghezza $\ell$ con pezzi di lunghezza al più $j$. Quanto vale $v(1,4)$?
$-\infty$
$1$
$10$
$4$
Spiegazione. Con soli pezzi di lunghezza $1$ l'asta si divide in $4$ pezzi da $1$: ricavo $4$. $10=v(4,4)$ usa anche pezzi di lunghezza $2$.
Nel taglio delle aste (RCP) un'asta di lunghezza $n$ ha $2^{n-1}$ schemi di taglio, perché in ogni posizione intera si taglia o no. Se invece l'ordine dei pezzi non conta (contano solo le lunghezze), quanti tagli distinti ha un'asta di lunghezza $5$?
$32$
$7$
$16$
$5$
Spiegazione. Sono le partizioni dell'intero $5$: $5$, $4+1$, $3+2$, $3+1+1$, $2+2+1$, $2+1+1+1$, $1+1+1+1+1$. Il ricavo dipende solo dalle lunghezze, quindi molti dei $16$ schemi sono equivalenti.
Il taglio delle aste (asta di lunghezza $n$, pezzo di lunghezza $j$ venduto a $p_j$) si può vedere come uno zaino illimitato. Con quali tipi di oggetto e quale vincolo?
Tipo $j$ con peso $j$ e profitto $p_j$, copie illimitate, peso totale esattamente $n$
Tipo $j$ con peso $p_j$ e profitto $j$, al più una copia, capacità $n$
Un solo tipo di peso $1$ e profitto $\max_j p_j$, capacità $n$
Tipo $j$ con peso $j$ e profitto $p_j$, al più una copia per tipo
Spiegazione. Ogni pezzo è una copia del tipo della sua lunghezza, e i pezzi devono coprire l'asta. Con un pezzo di lunghezza $1$ e prezzi non negativi, anche la versione «peso al più $n$» ha lo stesso ottimo.
Nel taglio delle aste (RCP: asta di lunghezza intera $n$, un pezzo di lunghezza $\ell$ vale $p_\ell$) una soluzione si codifica con $(x_1,\dots,x_n)$, $x_\ell$ = numero di pezzi di lunghezza $\ell$. Quali schemi di taglio hanno lo stesso vettore?
Nessuno: ogni schema ha un vettore diverso
Quelli con lo stesso numero di tagli
Quelli con lo stesso pezzo più lungo
Quelli che producono gli stessi pezzi in ordine diverso, e hanno lo stesso profitto
Spiegazione. Il vettore conta i pezzi per lunghezza, non l'ordine dei tagli: per $n=4$ i tagli $1+3$ e $3+1$ danno lo stesso vettore $(1,0,1,0)$. Per questo i $2^{n-1}$ schemi sono più dei vettori distinti.
Un'asta di lunghezza $n=4$ si taglia in pezzi interi; i pezzi valgono $p=(1,5,8,9)$ per lunghezza $\ell=1,2,3,4$. Quanti schemi di taglio ci sono (contando l'ordine) e qual è il profitto massimo?
$5$ schemi, profitto massimo $10$
$16$ schemi, profitto massimo $13$
$8$ schemi, profitto massimo $10$
$8$ schemi, profitto massimo $9$
Spiegazione. Ognuna delle $n-1=3$ posizioni si taglia o no: $2^3=8$. Il massimo è $5+5=10$ con due pezzi da $2$; l'asta intera vale $9$, $1+8=9$.
La PD per il taglio delle aste calcola $v(k)=\max_{1\le\ell\le k}\{p_\ell+v(k-\ell)\}$ per $k=1,\dots,n$. Quanti passi esegue, e perché non è solo pseudo-polinomiale come la PD dello zaino?
$\Theta(n^2)$, ma pseudo-polinomiale perché dipende da $n$
$\Theta(n^2)$; l'input contiene $n$ prezzi, quindi è polinomiale nella dimensione
$\Theta(2^n)$, come l'enumerazione degli schemi
$\Theta(n)$, un passo per lunghezza
Spiegazione. Per ogni $k$ si provano $k$ primi pezzi: $\sum_kk=\Theta(n^2)$. Qui $n$ è anche il numero di dati (i prezzi $p_1,\dots,p_n$), quindi $\Theta(n^2)$ è polinomiale nella dimensione dell'istanza.
Il taglio delle aste ha due algoritmi di PD: il primo sceglie il primo pezzo tagliato, il secondo tratta le lunghezze $\ell=1,\dots,n$ come tipi di oggetto di uno zaino illimitato di capacità $n$. Quanti passi esegue il secondo?
$\Theta(n^2)$, come il primo: $n$ tipi per $n+1$ capacità
$\Theta(n)$
$\Theta(n^3)$
$\Theta(2^n)$
Spiegazione. La PD dello zaino illimitato esegue $\Theta(\text{tipi}\cdot\text{capacità})$ passi, qui $\Theta(n\cdot n)$. I due algoritmi hanno lo stesso ordine di crescita.
Un'asta di lunghezza intera $n=5$ si taglia in pezzi di lunghezza intera, decidendo per ognuna delle $n-1$ posizioni intermedie se tagliare. Quanti schemi di taglio ci sono, contando l'ordine dei pezzi?
$7$
$120$
$16$
$32$
Spiegazione. $2^{n-1}=2^4=16$. I vettori distinti di pezzi (partizioni del numero $5$) sono solo $7$, perché l'ordine non conta.
Taglio delle aste con $n=5$ e prezzi $p=(1,5,8,9,10)$ per le lunghezze $1,\dots,5$. I tagli producono i pezzi $2,1,2$. Qual è il vettore $(x_1,\dots,x_5)$ e quale il profitto?
$(0,1,0,0,1)$, profitto $15$
$(1,2,0,0,0)$, profitto $11$
$(2,1,0,0,0)$, profitto $7$
$(1,2,0,0,0)$, profitto $3$
Spiegazione. Un pezzo di lunghezza $1$ e due di lunghezza $2$: $1\cdot1+2\cdot2=5$ e profitto $1+2\cdot5=11$.
La prima PD per il taglio delle aste calcola $v(k)=\max_{1\le\ell\le k}\{p_\ell+v(k-\ell)\}$, con $v(0)=0$. Con prezzi $p=(1,5,8,9)$, quanto vale $v(4)$?
Nella prima PD per il taglio delle aste il calcolo di $v(k)$ prova $k$ lunghezze del primo pezzo. Quante prove in tutto per un'asta di lunghezza $n=4$?
$16$
$4$
$8$
$10$
Spiegazione. $1+2+3+4=n(n+1)/2=10$: da qui $\Theta(n^2)$, mentre gli schemi di taglio sono $2^{n-1}$, molti di più per $n$ grande.
La seconda PD per il taglio delle aste tratta le lunghezze $\ell=1,\dots,n$ come tipi di oggetto (peso $\ell$, profitto $p_\ell$) di uno zaino illimitato di capacità $n$. Perché illimitato e non 0/1?
Perché ogni lunghezza si usa al più una volta
Perché i prezzi sono interi
Si possono tagliare più pezzi della stessa lunghezza
Perché l'asta può essere più lunga di $n$
Spiegazione. Per esempio $n=4$ con due pezzi da $2$: due copie dello stesso tipo. Con $n$ tipi e capacità $n$ il numero di passi è $\Theta(n^2)$.
Nella seconda PD per il taglio delle aste (zaino illimitato con i tipi $\ell=1,\dots,n$ e capacità $n$) si aggiorna una cella per ogni coppia (tipo, capacità $1,\dots,n$). Quante coppie ci sono per $n=4$?
$8$
$16$
$10$
$20$
Spiegazione. $4$ tipi per $4$ capacità positive: $16$ aggiornamenti, $\Theta(n^2)$ come la prima PD.
Nel taglio delle aste (RCP) con un'asta di lunghezza $n$ e profitti $p_1,\dots,p_n$, la PD $v(\ell)=\max_{j\le\ell}\{p_j+v(\ell-j)\}$ esegue $\Theta(n^2)$ passi. Perché è un tempo polinomiale?
Perché i profitti sono interi
Perché $n$ si scrive con $\log n$ bit
Perché la ricorrenza ha un solo caso base
L'input contiene $n$ profitti: $n$ è anche il numero dei dati
Spiegazione. A differenza di $c$ nello zaino, $n$ conta i valori dell'input: $\Theta(n^2)$ è polinomiale nella sua dimensione.
Nella PD per il taglio delle aste, $v(\ell)=\max_{j\le\ell}\{p_j+v(\ell-j)\}$: quale ipotesi sui pezzi permette di usare la stessa ricorrenza per l'asta residua $\ell-j$?
I profitti crescono con la lunghezza
L'asta va tagliata in due pezzi
Ogni lunghezza si può tagliare quante volte si vuole
Ogni lunghezza al più una volta
Spiegazione. Il pezzo di lunghezza $j$ resta disponibile: l'asta residua è lo stesso problema con lunghezza $\ell-j$.
Dopo la PD per il taglio delle aste il vettore $s$ contiene, per ogni lunghezza $\ell$, il primo pezzo scelto. Che cosa si ottiene, senza calcoli in più?
Una soluzione ottima per ogni lunghezza $\ell\le n$
Solo la soluzione per la lunghezza $n$
Tutte le soluzioni ottime
Un bound sul valore ottimo
Spiegazione. Per ogni $\ell$ si ripercorre $s[\ell], s[\ell-s[\ell]],\dots$ fino a $0$.
Nella PD per il taglio delle aste, perché $v(0)=0$?
Perché $p_0=0$ è un dato
Perché l'asta va tagliata almeno una volta
Perché il profitto massimo è $0$
Un'asta di lunghezza $0$ non dà pezzi né profitto
Spiegazione. È il caso base: senza asta non c'è nulla da vendere.
Domande generate (25)
Ogni generatore crea a ogni avvio un'istanza nuova, con numeri diversi: qui alcuni esempi.
2. PD per il problema dello zaino 0/1 (2)
Esempio 1 · dp-g-kp-dp-cella · livello facile · dispensa
Problema dello zaino 0-1 (KP) con oggetti $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 4 & 3 & 6 & 4\\ w_j & 6 & 3 & 2 & 4\end{array}$ e capacità $c=9$; $v(j,k)$ è il massimo profitto con gli oggetti $1,\dots,j$ e capacità $k$, con $v(0,k)=0$. Con la ricorsione $v(j,k)=\max\{v(j-1,k),\,p_j+v(j-1,k-w_j)\}$ (il secondo termine solo se $w_j\le k$), quanto vale $v(3,7)$?
$13$
$4$
$9$
$18$
Spiegazione. $v(3,7)$ è il profitto massimo con gli oggetti $\{1,2,3\}$ e capacità $7$: vale $9$. Ogni oggetto si usa al più una volta (con ripetizioni si otterrebbe $18$, il valore dello zaino illimitato).
Esempio 2 · dp-g-kp-dp-cella · livello facile · dispensa
Problema dello zaino 0-1 (KP) con oggetti $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 11 & 3 & 11 & 9\\ w_j & 3 & 3 & 3 & 5\end{array}$ e capacità $c=11$; $v(j,k)$ è il massimo profitto con gli oggetti $1,\dots,j$ e capacità $k$, con $v(0,k)=0$. Con la ricorsione $v(j,k)=\max\{v(j-1,k),\,p_j+v(j-1,k-w_j)\}$ (il secondo termine solo se $w_j\le k$), quanto vale $v(3,10)$?
$25$
$14$
$34$
$33$
Spiegazione. $v(3,10)$ è il profitto massimo con gli oggetti $\{1,2,3\}$ e capacità $10$: vale $25$. Ogni oggetto si usa al più una volta (con ripetizioni si otterrebbe $33$, il valore dello zaino illimitato).
Esempio 1 · dp-g-kp-dp-completa · livello complessa · dispensa
Problema dello zaino 0-1 (KP: si sceglie un sottoinsieme di oggetti di profitto massimo con peso totale al più $c$) con capacità $c=11$: $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 10 & 14 & 13 & 11\\ w_j & 4 & 5 & 2 & 5\end{array}$. Si calcola la tabella della PD, $v(j,k)$ = massimo profitto con gli oggetti $1,\dots,j$ e capacità $k$, e si ricostruisce una soluzione ottima risalendo da $(4,11)$. Quali sono il valore ottimo e l'insieme ottimo $\tilde S$?
$v(4,11)=27$, $\tilde S=\{2,3\}$
$v(4,11)=25$, $\tilde S=\{2,4\}$
$v(4,11)=34$, $\tilde S=\{1,3,4\}$
$v(4,11)=37$, $\tilde S=\{1,2,3\}$
Spiegazione. La tabella dà $v(4,11)=37$; risalendo da $(4,11)$ (l'oggetto $j$ è scelto se $v(j,k)\ne v(j-1,k)$) si ottiene $\tilde S=\{1,2,3\}$. Il greedy per efficienza dà solo $37$.
Esempio 2 · dp-g-kp-dp-completa · livello complessa · dispensa
Problema dello zaino 0-1 (KP: si sceglie un sottoinsieme di oggetti di profitto massimo con peso totale al più $c$) con capacità $c=11$: $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 13 & 4 & 14 & 11\\ w_j & 3 & 3 & 3 & 5\end{array}$. Si calcola la tabella della PD, $v(j,k)$ = massimo profitto con gli oggetti $1,\dots,j$ e capacità $k$, e si ricostruisce una soluzione ottima risalendo da $(4,11)$. Quali sono il valore ottimo e l'insieme ottimo $\tilde S$?
$v(4,11)=38$, $\tilde S=\{1,3,4\}$
$v(4,11)=29$, $\tilde S=\{2,3,4\}$
$v(4,11)=31$, $\tilde S=\{1,2,3\}$
$v(4,11)=28$, $\tilde S=\{1,2,4\}$
Spiegazione. La tabella dà $v(4,11)=38$; risalendo da $(4,11)$ (l'oggetto $j$ è scelto se $v(j,k)\ne v(j-1,k)$) si ottiene $\tilde S=\{1,3,4\}$. Il greedy per efficienza dà solo $38$.
3. PD per il problema dello zaino illimitato (2)
Esempio 1 · dp-g-ukp-dp · livello facile · dispensa
Zaino illimitato (UKP): $n=3$ tipi di oggetto, ciascuno disponibile in copie illimitate, $\begin{array}{c|ccc}j & 1 & 2 & 3\\ \hline p_j & 10 & 18 & 21\\ w_j & 3 & 5 & 7\end{array}$, capacità $c=12$. $v(k)$ è il massimo profitto con capacità $k$: $v(0)=0$ e $v(k)=\max_{j:\,w_j\le k}\{p_j+v(k-w_j)\}$ (uguale a $0$ se nessun tipo entra). Quanto vale $v(12)$?
$36$
$40$
$39$
$38$
Spiegazione. La tabella dà $v(12)=40$. Ogni tipo può essere usato più volte: il valore $39$ è quello del KP 0/1, e il greedy per efficienza con ripetizioni ($36$) non è in generale ottimo.
Esempio 2 · dp-g-ukp-dp · livello facile · dispensa
Zaino illimitato (UKP): $n=3$ tipi di oggetto, ciascuno disponibile in copie illimitate, $\begin{array}{c|ccc}j & 1 & 2 & 3\\ \hline p_j & 10 & 12 & 7\\ w_j & 4 & 6 & 3\end{array}$, capacità $c=14$. $v(k)$ è il massimo profitto con capacità $k$: $v(0)=0$ e $v(k)=\max_{j:\,w_j\le k}\{p_j+v(k-w_j)\}$ (uguale a $0$ se nessun tipo entra). Quanto vale $v(14)$?
$29$
$31$
$34$
$30$
Spiegazione. La tabella dà $v(14)=34$. Ogni tipo può essere usato più volte: il valore $29$ è quello del KP 0/1, e il greedy per efficienza con ripetizioni ($30$) non è in generale ottimo.
Esempio 1 · dp-g-ukp-sol · livello media · dispensa
Zaino illimitato (UKP): $n=3$ tipi di oggetto, ciascuno in copie illimitate, $\begin{array}{c|ccc}j & 1 & 2 & 3\\ \hline p_j & 11 & 9 & 13\\ w_j & 4 & 6 & 5\end{array}$, capacità $c=10$; $x_j$ è il numero di copie del tipo $j$. Qual è il valore ottimo, e con quale vettore $x$ (unico) si ottiene?
$22$ con $x=(2,0,0)$
$24$ con $x=(1,0,1)$
$26$ con $x=(0,0,2)$
$26$ con $x=(2,0,0)$
Spiegazione. La PD $v(k)=\max_j\{p_j+v(k-w_j)\}$ dà $v(10)=26$, ottenuto con $x=(0,0,2)$. Il greedy per efficienza con ripetizioni dà $22$ e lo zaino 0-1 $24$.
Esempio 2 · dp-g-ukp-sol · livello media · dispensa
Zaino illimitato (UKP): $n=3$ tipi di oggetto, ciascuno in copie illimitate, $\begin{array}{c|ccc}j & 1 & 2 & 3\\ \hline p_j & 11 & 6 & 12\\ w_j & 4 & 5 & 5\end{array}$, capacità $c=15$; $x_j$ è il numero di copie del tipo $j$. Qual è il valore ottimo, e con quale vettore $x$ (unico) si ottiene?
$36$ con $x=(0,0,3)$
$33$ con $x=(3,0,0)$
$29$ con $x=(1,1,1)$
$36$ con $x=(3,0,0)$
Spiegazione. La PD $v(k)=\max_j\{p_j+v(k-w_j)\}$ dà $v(15)=36$, ottenuto con $x=(0,0,3)$. Il greedy per efficienza con ripetizioni dà $33$ e lo zaino 0-1 $29$.
4. PD per il problema dello zaino limitato (2)
Esempio 1 · dp-g-bkp-dp · livello facile · dispensa
Zaino limitato (BKP): il tipo $j$ ha profitto $p_j$, peso $w_j$ e $b_j$ copie disponibili, $\begin{array}{c|ccc}j & 1 & 2 & 3\\ \hline p_j & 4 & 3 & 4\\ w_j & 5 & 2 & 4\\ b_j & 1 & 1 & 2\end{array}$, capacità $c=10$. Con $v(j,k)=\max_{0\le d\le\min\{b_j,\lfloor k/w_j\rfloor\}}\{d\,p_j+v(j-1,k-d\,w_j)\}$ e $v(0,k)=0$, quanto vale il valore ottimo $v(3,10)$?
$12$
$8$
$11$
$15$
Spiegazione. La PD dà $v(3,10)=11$. Con una sola copia per tipo (KP) si avrebbe $8$, con copie illimitate (UKP) $15$.
Esempio 2 · dp-g-bkp-dp · livello facile · dispensa
Zaino limitato (BKP): il tipo $j$ ha profitto $p_j$, peso $w_j$ e $b_j$ copie disponibili, $\begin{array}{c|ccc}j & 1 & 2 & 3\\ \hline p_j & 11 & 6 & 9\\ w_j & 3 & 2 & 5\\ b_j & 1 & 3 & 3\end{array}$, capacità $c=11$. Con $v(j,k)=\max_{0\le d\le\min\{b_j,\lfloor k/w_j\rfloor\}}\{d\,p_j+v(j-1,k-d\,w_j)\}$ e $v(0,k)=0$, quanto vale il valore ottimo $v(3,11)$?
$29$
$26$
$30$
$39$
Spiegazione. La PD dà $v(3,11)=29$. Con una sola copia per tipo (KP) si avrebbe $26$, con copie illimitate (UKP) $39$.
Esempio 1 · dp-g-bkp-cella · livello media · dispensa
Zaino limitato (BKP): il tipo $j$ ha profitto $p_j$, peso $w_j$ e $b_j$ copie, $\begin{array}{c|ccc}j & 1 & 2 & 3\\ \hline p_j & 5 & 6 & 7\\ w_j & 2 & 2 & 2\\ b_j & 1 & 2 & 2\end{array}$, capacità $c=11$. $v(j,k)$ è il massimo profitto con i soli tipi $1,\dots,j$ e capacità $k$, con al più $b_j$ copie del tipo $j$. Quanto vale $v(2,5)$?
$11$
$5$
$12$
$14$
Spiegazione. Con i tipi $1$ e $2$ e capacità $5$, rispettando i limiti $b_1=1$ e $b_2=2$, il massimo è $12$. Senza limiti sulle copie si avrebbe $12$.
Esempio 2 · dp-g-bkp-cella · livello media · dispensa
Zaino limitato (BKP): il tipo $j$ ha profitto $p_j$, peso $w_j$ e $b_j$ copie, $\begin{array}{c|ccc}j & 1 & 2 & 3\\ \hline p_j & 11 & 6 & 9\\ w_j & 3 & 2 & 5\\ b_j & 1 & 3 & 3\end{array}$, capacità $c=12$. $v(j,k)$ è il massimo profitto con i soli tipi $1,\dots,j$ e capacità $k$, con al più $b_j$ copie del tipo $j$. Quanto vale $v(2,10)$?
$11$
$29$
$34$
$17$
Spiegazione. Con i tipi $1$ e $2$ e capacità $10$, rispettando i limiti $b_1=1$ e $b_2=3$, il massimo è $29$. Senza limiti sulle copie si avrebbe $34$.
5. PD per il problema del subset sum (2)
Esempio 1 · dp-g-ssp-dp · livello facile · dispensa
Subset sum: pesi $w=(12,3,6,11,9)$ e valore obiettivo $c=28$. $r(j,k)$ è vero se un sottoinsieme dei primi $j$ pesi ha somma esattamente $k$: $r(0,0)$ vero, $r(0,k)$ falso per $k\ge 1$, e $r(j,k)=r(j-1,k)\lor r(j-1,k-w_j)$ (il secondo termine solo se $w_j\le k$). Qual è il più grande $k\le c$ con $r(5,k)=\textit{true}$?
$27$
$26$
$21$
$18$
Spiegazione. Le somme raggiungibili non superiori a $28$ hanno massimo $27$; $c=28$ non è raggiungibile. Le scelte greedy (per peso decrescente: $26$) non garantiscono il massimo.
Esempio 2 · dp-g-ssp-dp · livello facile · dispensa
Subset sum: pesi $w=(12,10,14,12,10)$ e valore obiettivo $c=27$. $r(j,k)$ è vero se un sottoinsieme dei primi $j$ pesi ha somma esattamente $k$: $r(0,0)$ vero, $r(0,k)$ falso per $k\ge 1$, e $r(j,k)=r(j-1,k)\lor r(j-1,k-w_j)$ (il secondo termine solo se $w_j\le k$). Qual è il più grande $k\le c$ con $r(5,k)=\textit{true}$?
$20$
$22$
$26$
$27$
Spiegazione. Le somme raggiungibili non superiori a $27$ hanno massimo $26$; $c=27$ non è raggiungibile. Le scelte greedy (per peso decrescente: $26$) non garantiscono il massimo.
Esempio 1 · dp-g-ssp-count · livello media · dispensa
Subset sum con pesi $w=(6,6,8,8)$ e obiettivo $c=10$. $r(j,k)$ è vero se un sottoinsieme dei primi $j$ pesi ha somma esattamente $k$ (il sottoinsieme vuoto dà $k=0$). Per quanti valori $k\in\{0,1,\dots,10\}$ la cella $r(4,k)$ è vera?
$3$
$5$
$2$
$11$
Spiegazione. Le somme raggiungibili fino a $10$ sono $3$, compreso $k=0$. Sottoinsiemi diversi possono dare la stessa somma: i sottoinsiemi con somma al più $10$ sono $5$.
Esempio 2 · dp-g-ssp-count · livello media · dispensa
Subset sum con pesi $w=(5,8,4,2)$ e obiettivo $c=13$. $r(j,k)$ è vero se un sottoinsieme dei primi $j$ pesi ha somma esattamente $k$ (il sottoinsieme vuoto dà $k=0$). Per quanti valori $k\in\{0,1,\dots,13\}$ la cella $r(4,k)$ è vera?
$12$
$11$
$14$
$13$
Spiegazione. Le somme raggiungibili fino a $13$ sono $12$, compreso $k=0$. Sottoinsiemi diversi possono dare la stessa somma: i sottoinsiemi con somma al più $13$ sono $12$.
6. PD per il problema dello zaino a scelta multipla (2)
Esempio 1 · dp-g-mckp-dp · livello facile · dispensa
Zaino a scelta multipla (MCKP): classi $\mathscr{J}_1=\{1,2\}$, $\mathscr{J}_2=\{3,4\}$, $\mathscr{J}_3=\{5,6\}$, oggetti $\begin{array}{c|cccccc}j & 1 & 2 & 3 & 4 & 5 & 6\\ \hline p_j & 2 & 4 & 3 & 5 & 2 & 3\\ w_j & 1 & 4 & 3 & 5 & 4 & 6\end{array}$, capacità $c=10$; si sceglie esattamente un oggetto per classe. Con $v(h,k)=\max_{j\in\mathscr{J}_h:\,w_j\le k}\{p_j+v(h-1,k-w_j)\}$, $v(0,k)=0$, quanto vale il valore ottimo $v(3,10)$?
$8$
$7$
$9$
$12$
Spiegazione. Il valore ottimo è $9$. Ignorando la capacità si prenderebbe il miglior oggetto di ogni classe ($12$); con «al più un oggetto per classe» si risolverebbe un altro problema ($9$).
Esempio 2 · dp-g-mckp-dp · livello facile · dispensa
Zaino a scelta multipla (MCKP): classi $\mathscr{J}_1=\{1,2\}$, $\mathscr{J}_2=\{3,4\}$, $\mathscr{J}_3=\{5,6\}$, oggetti $\begin{array}{c|cccccc}j & 1 & 2 & 3 & 4 & 5 & 6\\ \hline p_j & 2 & 6 & 7 & 2 & 6 & 9\\ w_j & 6 & 5 & 5 & 1 & 1 & 2\end{array}$, capacità $c=9$; si sceglie esattamente un oggetto per classe. Con $v(h,k)=\max_{j\in\mathscr{J}_h:\,w_j\le k}\{p_j+v(h-1,k-w_j)\}$, $v(0,k)=0$, quanto vale il valore ottimo $v(3,9)$?
$17$
$16$
$22$
$14$
Spiegazione. Il valore ottimo è $17$. Ignorando la capacità si prenderebbe il miglior oggetto di ogni classe ($22$); con «al più un oggetto per classe» si risolverebbe un altro problema ($17$).
Esempio 1 · dp-g-mckp-sol · livello media · dispensa
Zaino a scelta multipla (MCKP): classi $\mathscr{J}_1=\{1,2\}$, $\mathscr{J}_2=\{3,4\}$, $\mathscr{J}_3=\{5,6\}$, oggetti $\begin{array}{c|cccccc}j & 1 & 2 & 3 & 4 & 5 & 6\\ \hline p_j & 6 & 8 & 2 & 6 & 9 & 9\\ w_j & 4 & 6 & 5 & 4 & 1 & 2\end{array}$, capacità $c=11$; si sceglie esattamente un oggetto per classe. Quale scelta di oggetti è ottima (la soluzione ottima è unica), e quanto vale?
$\{1,4,5\}$, valore $21$
$\{1,4,6\}$, valore $21$
$\{1,3,5\}$, valore $17$
$\{2,4,5\}$, valore $23$
Spiegazione. La PD per classi e la ricostruzione all'indietro danno $\{2,4,5\}$, di valore $23$; la seconda migliore scelta ammissibile vale $21$.
Esempio 2 · dp-g-mckp-sol · livello media · dispensa
Zaino a scelta multipla (MCKP): classi $\mathscr{J}_1=\{1,2\}$, $\mathscr{J}_2=\{3,4\}$, $\mathscr{J}_3=\{5,6\}$, oggetti $\begin{array}{c|cccccc}j & 1 & 2 & 3 & 4 & 5 & 6\\ \hline p_j & 5 & 4 & 5 & 8 & 9 & 7\\ w_j & 6 & 1 & 6 & 4 & 5 & 6\end{array}$, capacità $c=15$; si sceglie esattamente un oggetto per classe. Quale scelta di oggetti è ottima (la soluzione ottima è unica), e quanto vale?
$\{2,3,5\}$, valore $18$
$\{2,4,5\}$, valore $21$
$\{2,4,6\}$, valore $19$
$\{1,4,5\}$, valore $22$
Spiegazione. La PD per classi e la ricostruzione all'indietro danno $\{1,4,5\}$, di valore $22$; la seconda migliore scelta ammissibile vale $21$.
7. PD per il problema dello zaino multidimensionale (2)
Esempio 1 · dp-g-mdkp-dp · livello facile · dispensa
Zaino multidimensionale (MDKP) con due dimensioni di capacità $c_1=8$ e $c_2=9$; l'oggetto $j$ ha profitto $p_j$ e pesi $w_{1j}$, $w_{2j}$: $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 4 & 8 & 3 & 8\\ w_{1j} & 4 & 3 & 4 & 6\\ w_{2j} & 5 & 2 & 4 & 2\end{array}$. Ogni oggetto si prende al più una volta. Con la PD $v(j,(k_1,k_2))$ su entrambe le capacità, quanto vale il valore ottimo?
$12$
$13$
$20$
$16$
Spiegazione. Il valore ottimo è $12$. Considerando una sola dimensione si otterrebbe $12$ o $20$, e sommando i vincoli $16$: sono rilassamenti, non soluzioni dell'MDKP.
Esempio 2 · dp-g-mdkp-dp · livello facile · dispensa
Zaino multidimensionale (MDKP) con due dimensioni di capacità $c_1=9$ e $c_2=11$; l'oggetto $j$ ha profitto $p_j$ e pesi $w_{1j}$, $w_{2j}$: $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 5 & 8 & 5 & 10\\ w_{1j} & 2 & 4 & 4 & 6\\ w_{2j} & 6 & 3 & 1 & 4\end{array}$. Ogni oggetto si prende al più una volta. Con la PD $v(j,(k_1,k_2))$ su entrambe le capacità, quanto vale il valore ottimo?
$16$
$23$
$18$
$15$
Spiegazione. Il valore ottimo è $15$. Considerando una sola dimensione si otterrebbe $15$ o $23$, e sommando i vincoli $18$: sono rilassamenti, non soluzioni dell'MDKP.
Esempio 1 · dp-g-mdkp-sol · livello media · dispensa
Zaino multidimensionale (MDKP) con due dimensioni di capacità $c_1=8$ e $c_2=7$; l'oggetto $j$ ha profitto $p_j$ e pesi $w_{1j}$, $w_{2j}$: $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 7 & 9 & 7 & 3\\ w_{1j} & 4 & 1 & 4 & 6\\ w_{2j} & 5 & 5 & 6 & 2\end{array}$. Ogni oggetto si prende al più una volta. Quale insieme di oggetti è la soluzione ottima (unica)?
$\{1\}$
$\{2\}$
$\{1,2\}$
$\{2,4\}$
Spiegazione. $\{2,4\}$ rispetta entrambe le capacità e vale $12$; la seconda migliore soluzione ammissibile vale $9$.
Esempio 2 · dp-g-mdkp-sol · livello media · dispensa
Zaino multidimensionale (MDKP) con due dimensioni di capacità $c_1=9$ e $c_2=10$; l'oggetto $j$ ha profitto $p_j$ e pesi $w_{1j}$, $w_{2j}$: $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 10 & 8 & 7 & 5\\ w_{1j} & 6 & 2 & 1 & 2\\ w_{2j} & 5 & 4 & 1 & 1\end{array}$. Ogni oggetto si prende al più una volta. Quale insieme di oggetti è la soluzione ottima (unica)?
$\{1,2,3\}$
$\{2,3,4\}$
$\{1,2\}$
$\{1,3,4\}$
Spiegazione. $\{1,2,3\}$ rispetta entrambe le capacità e vale $25$; la seconda migliore soluzione ammissibile vale $22$.
8. PD per il problema dello zaino con setup (2)
Esempio 1 · dp-g-kps-dp · livello facile · dispensa
Zaino con setup (KPS): classi $\mathscr{J}_1=\{1,2\}$ e $\mathscr{J}_2=\{3,4\}$, oggetti $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 6 & 8 & 3 & 7\\ w_j & 3 & 5 & 5 & 4\end{array}$, capacità $c=9$. Usare la classe $h$ costa una volta il profitto di setup $f_h$ e il peso di setup $s_h$, con $f=(4,1)$ e $s=(3,1)$; si massimizza il profitto degli oggetti meno i setup pagati. Quanto vale il valore ottimo?
$8$
$10$
$7$
$6$
Spiegazione. Il valore ottimo è $6$. Dimenticare i costi di setup dà $8$, dimenticare i pesi di setup $10$, pagare il setup per ogni oggetto $6$.
Esempio 2 · dp-g-kps-dp · livello facile · dispensa
Zaino con setup (KPS): classi $\mathscr{J}_1=\{1,2\}$ e $\mathscr{J}_2=\{3,4\}$, oggetti $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 5 & 5 & 5 & 8\\ w_j & 5 & 1 & 5 & 4\end{array}$, capacità $c=11$. Usare la classe $h$ costa una volta il profitto di setup $f_h$ e il peso di setup $s_h$, con $f=(4,4)$ e $s=(2,3)$; si massimizza il profitto degli oggetti meno i setup pagati. Quanto vale il valore ottimo?
$5$
$13$
$10$
$6$
Spiegazione. Il valore ottimo è $6$. Dimenticare i costi di setup dà $13$, dimenticare i pesi di setup $10$, pagare il setup per ogni oggetto $5$.
Esempio 1 · dp-g-kps-sol · livello media · dispensa
Zaino con setup (KPS): classi $\mathscr{J}_1=\{1,2\}$ e $\mathscr{J}_2=\{3,4\}$, oggetti $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 6 & 8 & 3 & 7\\ w_j & 3 & 5 & 5 & 4\end{array}$, capacità $c=9$. Usare la classe $h$ costa una volta il profitto di setup $f_h$ e il peso di setup $s_h$, con $f=(4,1)$ e $s=(3,1)$; si massimizza il profitto degli oggetti meno i setup pagati. Quale insieme di oggetti è la soluzione ottima (unica)?
$\{2\}$
$\{1\}$
$\{3\}$
$\{4\}$
Spiegazione. $\{4\}$ vale $6$, setup compresi; la seconda migliore soluzione vale $4$.
Esempio 2 · dp-g-kps-sol · livello media · dispensa
Zaino con setup (KPS): classi $\mathscr{J}_1=\{1,2\}$ e $\mathscr{J}_2=\{3,4\}$, oggetti $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 5 & 5 & 5 & 8\\ w_j & 5 & 1 & 5 & 4\end{array}$, capacità $c=11$. Usare la classe $h$ costa una volta il profitto di setup $f_h$ e il peso di setup $s_h$, con $f=(4,4)$ e $s=(2,3)$; si massimizza il profitto degli oggetti meno i setup pagati. Quale insieme di oggetti è la soluzione ottima (unica)?
$\{2,3\}$
$\{2,4\}$
$\{4\}$
$\{1,2\}$
Spiegazione. $\{1,2\}$ vale $6$, setup compresi; la seconda migliore soluzione vale $5$.
9. PD per il problema degli zaini multipli (2)
Esempio 1 · dp-g-mkp-dp · livello facile · dispensa
Zaino multiplo (MKP): due zaini di capacità $c_1=5$ e $c_2=7$, oggetti $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 5 & 6 & 6 & 5\\ w_j & 2 & 4 & 4 & 2\end{array}$; ogni oggetto va in al più uno zaino. Con la PD sugli stati $(j,(k_1,k_2))$ delle capacità residue, quanto vale il valore ottimo?
$22$
$17$
$16$
$11$
Spiegazione. Il valore ottimo è $17$. Un solo zaino di capacità $12$ darebbe $22$: è un upper bound, perché quella soluzione non si divide fra i due zaini.
Esempio 2 · dp-g-mkp-dp · livello facile · dispensa
Zaino multiplo (MKP): due zaini di capacità $c_1=8$ e $c_2=7$, oggetti $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 6 & 5 & 6 & 9\\ w_j & 5 & 2 & 5 & 4\end{array}$; ogni oggetto va in al più uno zaino. Con la PD sugli stati $(j,(k_1,k_2))$ delle capacità residue, quanto vale il valore ottimo?
$20$
$21$
$19$
$14$
Spiegazione. Il valore ottimo è $20$. Un solo zaino di capacità $15$ darebbe $21$: è un upper bound, perché quella soluzione non si divide fra i due zaini.
Esempio 1 · dp-g-mkp-sol · livello media · dispensa
Zaino multiplo (MKP): due zaini di capacità $c_1=6$ e $c_2=6$, oggetti $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 10 & 5 & 3 & 7\\ w_j & 2 & 2 & 3 & 2\end{array}$; ogni oggetto va in al più uno zaino. Quale insieme di oggetti viene inserito negli zaini nella soluzione ottima (l'insieme ottimo è unico)?
$\{1,2,3\}$
$\{1,2,4\}$
$\{1,2,3,4\}$
$\{1,3,4\}$
Spiegazione. L'insieme $\{1,2,3,4\}$, di valore $25$, si divide fra i due zaini rispettando le capacità; il secondo miglior insieme vale $22$.
Esempio 2 · dp-g-mkp-sol · livello media · dispensa
Zaino multiplo (MKP): due zaini di capacità $c_1=8$ e $c_2=7$, oggetti $\begin{array}{c|cccc}j & 1 & 2 & 3 & 4\\ \hline p_j & 9 & 3 & 5 & 4\\ w_j & 4 & 5 & 2 & 5\end{array}$; ogni oggetto va in al più uno zaino. Quale insieme di oggetti viene inserito negli zaini nella soluzione ottima (l'insieme ottimo è unico)?
$\{1,2,3\}$
$\{1,4\}$
$\{1,3\}$
$\{1,3,4\}$
Spiegazione. L'insieme $\{1,3,4\}$, di valore $18$, si divide fra i due zaini rispettando le capacità; il secondo miglior insieme vale $17$.
10. PD per il problema del lot sizing senza capacità (3)
Esempio 1 · dp-g-uls-cjt · livello facile · dispensa
Lot sizing senza capacità (ULS): domanda $d_t$, costo di setup $sc_t$, costo variabile unitario $vc_t$ e costo unitario $hc_t$ della scorta a fine periodo $\begin{array}{c|cccc}t & 1 & 2 & 3 & 4\\ \hline d_t & 20 & 5 & 30 & 10\\ sc_t & 70 & 90 & 30 & 30\\ vc_t & 2 & 1 & 2 & 0\\ hc_t & 3 & 2 & 1 & 1\end{array}$. Quanto vale il costo $c_{2,4}$ del lotto prodotto nel periodo $2$ per coprire le domande dei periodi $2,\dots,4$ (setup, produzione e scorte)?
$225$
$135$
$275$
$205$
Spiegazione. $c_{j,t}=sc_j+vc_j\,D_{j,t}+\sum_{k=j}^{t-1}hc_k\,D_{k+1,t}=225$: alla fine di ogni periodo $k$ la scorta contiene le domande dei periodi successivi del lotto, non solo quella del periodo seguente.
Esempio 2 · dp-g-uls-cjt · livello facile · dispensa
Lot sizing senza capacità (ULS): domanda $d_t$, costo di setup $sc_t$, costo variabile unitario $vc_t$ e costo unitario $hc_t$ della scorta a fine periodo $\begin{array}{c|cccc}t & 1 & 2 & 3 & 4\\ \hline d_t & 15 & 15 & 30 & 25\\ sc_t & 90 & 90 & 90 & 40\\ vc_t & 0 & 2 & 1 & 2\\ hc_t & 1 & 2 & 3 & 3\end{array}$. Quanto vale il costo $c_{2,4}$ del lotto prodotto nel periodo $2$ per coprire le domande dei periodi $2,\dots,4$ (setup, produzione e scorte)?
$610$
$325$
$365$
$415$
Spiegazione. $c_{j,t}=sc_j+vc_j\,D_{j,t}+\sum_{k=j}^{t-1}hc_k\,D_{k+1,t}=415$: alla fine di ogni periodo $k$ la scorta contiene le domande dei periodi successivi del lotto, non solo quella del periodo seguente.
Esempio 1 · dp-g-uls-ww · livello media · dispensa
Lot sizing senza capacità (ULS) con $m=4$ periodi, costo di setup $sc_t=70$, costo variabile nullo e costo di mantenimento $hc_t=1$ per ogni periodo, e domande $\begin{array}{c|cccc}t & 1 & 2 & 3 & 4\\ \hline d_t & 25 & 35 & 35 & 5\end{array}$. Sia $c_{j,t}$ il costo del lotto prodotto in $j$ per i periodi $j,\dots,t$ e $v(t)$ il costo minimo per coprire i periodi $1,\dots,t$: $v(0)=0$ e $v(t)=\min_{1\le j\le t}\{v(j-1)+c_{j,t}\}$. Quanto vale il costo ottimo $v(4)$?
$180$
$190$
$280$
$245$
Spiegazione. $v=(0,70,105,175,180)$ per $t=0,\dots,4$; lotti nei periodi $1,3$. Un setup in ogni periodo costa $280$, un solo lotto nel periodo 1 costa $190$.
Esempio 2 · dp-g-uls-ww · livello media · dispensa
Lot sizing senza capacità (ULS) con $m=4$ periodi, costo di setup $sc_t=100$, costo variabile nullo e costo di mantenimento $hc_t=1$ per ogni periodo, e domande $\begin{array}{c|cccc}t & 1 & 2 & 3 & 4\\ \hline d_t & 35 & 30 & 40 & 35\end{array}$. Sia $c_{j,t}$ il costo del lotto prodotto in $j$ per i periodi $j,\dots,t$ e $v(t)$ il costo minimo per coprire i periodi $1,\dots,t$: $v(0)=0$ e $v(t)=\min_{1\le j\le t}\{v(j-1)+c_{j,t}\}$. Quanto vale il costo ottimo $v(4)$?
$265$
$400$
$310$
$315$
Spiegazione. $v=(0,100,130,210,265)$ per $t=0,\dots,4$; lotti nei periodi $1,3$. Un setup in ogni periodo costa $400$, un solo lotto nel periodo 1 costa $315$.
Esempio 1 · dp-g-uls-completa · livello complessa · dispensa
Lot sizing senza capacità (ULS) con costo variabile nullo, domanda $d_t$, costo di setup $sc_t$ e costo unitario $hc_t$ della scorta a fine periodo $\begin{array}{c|ccccc}t & 1 & 2 & 3 & 4 & 5\\ \hline d_t & 25 & 35 & 25 & 5 & 15\\ sc_t & 70 & 40 & 70 & 90 & 40\\ hc_t & 2 & 2 & 2 & 1 & 1\end{array}$. Con $c_{j,t}$ costo del lotto prodotto in $j$ per i periodi $j,\dots,t$, la PD è $v(0)=0$, $v(t)=\min_{1\le j\le t}\{v(j-1)+c_{j,t}\}$. Quali sono il costo ottimo $v(5)$ e i periodi dei lotti di produzione?
$v(5)=310$, lotti nei periodi $1,2,3,4,5$
$v(5)=220$, lotti nei periodi $1,2,5$
$v(5)=375$, lotti nei periodi $1$
$v(5)=230$, lotti nei periodi $1,2,3,5$
Spiegazione. $v=(0,70,110,160,180,220)$ per $t=0,\dots,5$; risalendo dagli argmin si trovano i lotti nei periodi $1,2,5$. Per la proprietà di Wagner e Whitin basta confrontare i lotti $c_{j,t}$.
Esempio 2 · dp-g-uls-completa · livello complessa · dispensa
Lot sizing senza capacità (ULS) con costo variabile nullo, domanda $d_t$, costo di setup $sc_t$ e costo unitario $hc_t$ della scorta a fine periodo $\begin{array}{c|ccccc}t & 1 & 2 & 3 & 4 & 5\\ \hline d_t & 40 & 10 & 5 & 10 & 35\\ sc_t & 80 & 70 & 40 & 40 & 50\\ hc_t & 2 & 2 & 1 & 2 & 2\end{array}$. Con $c_{j,t}$ costo del lotto prodotto in $j$ per i periodi $j,\dots,t$, la PD è $v(0)=0$, $v(t)=\min_{1\le j\le t}\{v(j-1)+c_{j,t}\}$. Quali sono il costo ottimo $v(5)$ e i periodi dei lotti di produzione?
$v(5)=210$, lotti nei periodi $1,4,5$
$v(5)=200$, lotti nei periodi $1,3,5$
$v(5)=280$, lotti nei periodi $1,2,3,4,5$
$v(5)=415$, lotti nei periodi $1$
Spiegazione. $v=(0,80,100,120,150,200)$ per $t=0,\dots,5$; risalendo dagli argmin si trovano i lotti nei periodi $1,3,5$. Per la proprietà di Wagner e Whitin basta confrontare i lotti $c_{j,t}$.
11. PD per il problema del lot sizing capacitato (2)
Esempio 1 · dp-g-cls-dp · livello facile · dispensa
Lot sizing con capacità (CLS) su $3$ periodi: domanda $d_t$, capacità $cap_t$, costo di setup $sc_t$ (pagato se si produce nel periodo $t$) e costo $hc_t$ per unità di scorta a fine periodo, costo variabile nullo, scorte iniziale e finale nulle: $\begin{array}{c|ccc}t & 1 & 2 & 3\\ \hline d_t & 4 & 5 & 2\\ cap_t & 6 & 6 & 6\\ sc_t & 14 & 13 & 11\\ hc_t & 2 & 1 & 3\end{array}$. Con la PD sugli stati $(t,k)$ (periodo, scorta finale), quanto vale il costo ottimo $v(3,0)$?
$31$
$38$
$29$
$32$
Spiegazione. Il costo ottimo è $31$, con il piano $x=(5,6,0)$. Il piano lot-for-lot costa $38$; ignorando le capacità si otterrebbe $29$.
Esempio 2 · dp-g-cls-dp · livello facile · dispensa
Lot sizing con capacità (CLS) su $3$ periodi: domanda $d_t$, capacità $cap_t$, costo di setup $sc_t$ (pagato se si produce nel periodo $t$) e costo $hc_t$ per unità di scorta a fine periodo, costo variabile nullo, scorte iniziale e finale nulle: $\begin{array}{c|ccc}t & 1 & 2 & 3\\ \hline d_t & 2 & 2 & 5\\ cap_t & 7 & 7 & 6\\ sc_t & 8 & 13 & 12\\ hc_t & 1 & 2 & 3\end{array}$. Con la PD sugli stati $(t,k)$ (periodo, scorta finale), quanto vale il costo ottimo $v(3,0)$?
$23$
$33$
$22$
$25$
Spiegazione. Il costo ottimo è $22$, con il piano $x=(4,0,5)$. Il piano lot-for-lot costa $33$; ignorando le capacità si otterrebbe $22$.
Esempio 1 · dp-g-cls-plan · livello complessa · dispensa
Lot sizing con capacità (CLS) su $3$ periodi: domanda $d_t$, capacità $cap_t$, costo di setup $sc_t$ (pagato se si produce nel periodo $t$) e costo $hc_t$ per unità di scorta a fine periodo, costo variabile nullo, scorte iniziale e finale nulle: $\begin{array}{c|ccc}t & 1 & 2 & 3\\ \hline d_t & 3 & 1 & 5\\ cap_t & 5 & 7 & 3\\ sc_t & 13 & 11 & 14\\ hc_t & 3 & 2 & 1\end{array}$. Quale piano di produzione $x=(x_1,x_2,x_3)$ è ottimo (il piano ottimo è unico), e quanto costa?
$x=(3,3,3)$, costo $42$
$x=(5,4,0)$, costo $40$
$x=(3,6,0)$, costo $34$
$x=(4,5,0)$, costo $37$
Spiegazione. La PD sulle scorte e la ricostruzione danno $x=(3,6,0)$ con costo $34$; il secondo miglior piano costa $37$. Con le capacità la produzione può anticipare la domanda anche con scorta in ingresso positiva.
Esempio 2 · dp-g-cls-plan · livello complessa · dispensa
Lot sizing con capacità (CLS) su $3$ periodi: domanda $d_t$, capacità $cap_t$, costo di setup $sc_t$ (pagato se si produce nel periodo $t$) e costo $hc_t$ per unità di scorta a fine periodo, costo variabile nullo, scorte iniziale e finale nulle: $\begin{array}{c|ccc}t & 1 & 2 & 3\\ \hline d_t & 2 & 2 & 5\\ cap_t & 7 & 7 & 6\\ sc_t & 8 & 13 & 12\\ hc_t & 1 & 2 & 3\end{array}$. Quale piano di produzione $x=(x_1,x_2,x_3)$ è ottimo (il piano ottimo è unico), e quanto costa?
$x=(5,0,4)$, costo $25$
$x=(2,2,5)$, costo $33$
$x=(4,0,5)$, costo $22$
$x=(6,0,3)$, costo $28$
Spiegazione. La PD sulle scorte e la ricostruzione danno $x=(4,0,5)$ con costo $22$; il secondo miglior piano costa $25$. Con le capacità la produzione può anticipare la domanda anche con scorta in ingresso positiva.
12. PD per il problema del cambio monete (2)
Esempio 1 · dp-g-ccp-dp · livello facile · dispensa
Cambio monete (CCP): tagli $w=(1,5,12)$, disponibili in quantità illimitata; si vuole dare un resto di esattamente $c=21$ con il minimo numero di monete. $v(k)$ è il minimo numero di monete per il resto $k$: $v(0)=0$ e $v(k)=\min_{j:\,w_j\le k}\{1+v(k-w_j)\}$. Quanto vale $v(21)$?
$6$
$10$
$5$
$4$
Spiegazione. La PD dà $v(21)=5$ monete. Il greedy che usa sempre il taglio più grande ne usa $6$: con questi tagli non è ottimo.
Esempio 2 · dp-g-ccp-dp · livello facile · dispensa
Cambio monete (CCP): tagli $w=(1,6,9)$, disponibili in quantità illimitata; si vuole dare un resto di esattamente $c=22$ con il minimo numero di monete. $v(k)$ è il minimo numero di monete per il resto $k$: $v(0)=0$ e $v(k)=\min_{j:\,w_j\le k}\{1+v(k-w_j)\}$. Quanto vale $v(22)$?
$6$
$4$
$5$
$3$
Spiegazione. La PD dà $v(22)=4$ monete. Il greedy che usa sempre il taglio più grande ne usa $6$: con questi tagli non è ottimo.
Esempio 1 · dp-g-ccp-unreach · livello media · dispensa
Cambio monete (CCP) con tagli $w=(4,7)$ in quantità illimitata. $v(k)$ è il minimo numero di monete per dare esattamente il resto $k$: $v(0)=0$, $v(k)=\min_{j:\,w_j\le k}\{1+v(k-w_j)\}$, e $v(k)=+\infty$ se il resto non si può dare. Per quanti valori $k\in\{1,\dots,18\}$ si ha $v(k)=+\infty$?
$10$
$12$
$9$
$8$
Spiegazione. Calcolando $v(1),\dots,v(18)$ si trovano $9$ resti non ottenibili. Non basta escludere i multipli di $4$ e di $7$: anche le loro somme sono ottenibili.
Esempio 2 · dp-g-ccp-unreach · livello media · dispensa
Cambio monete (CCP) con tagli $w=(4,9)$ in quantità illimitata. $v(k)$ è il minimo numero di monete per dare esattamente il resto $k$: $v(0)=0$, $v(k)=\min_{j:\,w_j\le k}\{1+v(k-w_j)\}$, e $v(k)=+\infty$ se il resto non si può dare. Per quanti valori $k\in\{1,\dots,13\}$ si ha $v(k)=+\infty$?
$5$
$7$
$9$
$8$
Spiegazione. Calcolando $v(1),\dots,v(13)$ si trovano $8$ resti non ottenibili. Non basta escludere i multipli di $4$ e di $9$: anche le loro somme sono ottenibili.
13. PD per il problema del taglio delle aste (2)
Esempio 1 · dp-g-rcp-dp · livello facile · dispensa
Taglio delle aste (RCP): un'asta di lunghezza $n=6$ si taglia in pezzi di lunghezza intera, e il pezzo di lunghezza $j$ si vende a $p_j$: $\begin{array}{c|cccccc}j & 1 & 2 & 3 & 4 & 5 & 6\\ \hline p_j & 5 & 6 & 11 & 12 & 14 & 15\end{array}$. $v(\ell)$ è il massimo ricavo da un'asta di lunghezza $\ell$: $v(0)=0$ e $v(\ell)=\max_{1\le j\le \ell}\{p_j+v(\ell-j)\}$. Quanto vale $v(6)$?
$22$
$15$
$25$
$30$
Spiegazione. $v=(0,5,10,15,20,25,30)$ per $\ell=0,\dots,6$, quindi $v(6)=30$. Un solo taglio ($22$) o il pezzo di miglior rapporto $p_j/j$ ($30$) non bastano in generale.
Esempio 2 · dp-g-rcp-dp · livello facile · dispensa
Taglio delle aste (RCP): un'asta di lunghezza $n=6$ si taglia in pezzi di lunghezza intera, e il pezzo di lunghezza $j$ si vende a $p_j$: $\begin{array}{c|cccccc}j & 1 & 2 & 3 & 4 & 5 & 6\\ \hline p_j & 3 & 4 & 5 & 7 & 9 & 10\end{array}$. $v(\ell)$ è il massimo ricavo da un'asta di lunghezza $\ell$: $v(0)=0$ e $v(\ell)=\max_{1\le j\le \ell}\{p_j+v(\ell-j)\}$. Quanto vale $v(6)$?
$10$
$18$
$15$
$12$
Spiegazione. $v=(0,3,6,9,12,15,18)$ per $\ell=0,\dots,6$, quindi $v(6)=18$. Un solo taglio ($12$) o il pezzo di miglior rapporto $p_j/j$ ($18$) non bastano in generale.
Esempio 1 · dp-g-rcp-sol · livello media · dispensa
Taglio delle aste (RCP): un'asta di lunghezza $n=6$ si taglia in pezzi di lunghezza intera, e il pezzo di lunghezza $j$ si vende a $p_j$: $\begin{array}{c|cccccc}j & 1 & 2 & 3 & 4 & 5 & 6\\ \hline p_j & 3 & 7 & 12 & 13 & 18 & 22\end{array}$. Qual è il ricavo massimo e con quali pezzi (taglio ottimo unico, a meno dell'ordine)?
$22$: pezzi $6$
$24$: pezzi $3+3$
$18$: pezzi $1+1+1+1+1+1$
$22$: pezzi $3+2+1$
Spiegazione. La PD $v(\ell)=\max_j\{p_j+v(\ell-j)\}$ dà $v(6)=24$ con i pezzi $3+3$. Vendere l'asta intera dà $22$.
Esempio 2 · dp-g-rcp-sol · livello media · dispensa
Taglio delle aste (RCP): un'asta di lunghezza $n=5$ si taglia in pezzi di lunghezza intera, e il pezzo di lunghezza $j$ si vende a $p_j$: $\begin{array}{c|ccccc}j & 1 & 2 & 3 & 4 & 5\\ \hline p_j & 5 & 7 & 8 & 10 & 15\end{array}$. Qual è il ricavo massimo e con quali pezzi (taglio ottimo unico, a meno dell'ordine)?
$25$: pezzi $1+1+1+1+1$
$22$: pezzi $2+1+1+1$
$15$: pezzi $5$
$19$: pezzi $2+2+1$
Spiegazione. La PD $v(\ell)=\max_j\{p_j+v(\ell-j)\}$ dà $v(5)=25$ con i pezzi $1+1+1+1+1$. Vendere l'asta intera dà $15$.