← Torna al sito

Banca delle domande

315 domande fisse · 25 domande generate

Domande fisse (315)

1. Principi della programmazione dinamica (33)

dp-f-001 · livello facile · dispensa
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?
  1. Sottostruttura ottima e sottoproblemi sovrapposti
  2. Sottostruttura ottima e sottoproblemi indipendenti
  3. Funzione obiettivo lineare e vincoli interi
  4. 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.
dp-f-002 · livello facile · dispensa
In programmazione dinamica (PD), che cosa succede se un problema ha la sottostruttura ottima ma ogni sottoproblema compare una sola volta nella ricorsione?
  1. La tabella rende l'algoritmo polinomiale nella dimensione dell'input
  2. La ricorrenza diventa sbagliata e va corretta con più casi base
  3. La tabella va riempita dall'alto verso il basso, non dal basso
  4. 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.
dp-f-003 · livello facile · dispensa
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?
  1. Leggendo la sola tabella dei valori in avanti, dallo stato iniziale a quello finale
  2. Rieseguendo la ricorsione dall'alto verso il basso, senza alcuna memorizzazione
  3. Memorizzando le decisioni in un'altra tabella e leggendole a ritroso dallo stato finale
  4. 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).
dp-f-040 · livello facile · dispensa
Un algoritmo di programmazione dinamica (PD) segue il paradigma «dividi, conquista e combina». Che cosa dice il principio di combinazione?
  1. Si sceglie il sottoproblema migliore e si scartano gli altri
  2. Si costruisce una soluzione ottima del problema dalle soluzioni ottime dei sottoproblemi
  3. Si scompone il problema in sottoproblemi più piccoli dello stesso tipo
  4. 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.
dp-f-041 · livello facile · dispensa
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?
  1. Memorizza il valore ottimo di ogni sottoproblema in una tabella e lo riusa quando il sottoproblema ricompare
  2. Scarta a priori i sottoinsiemi con profitto basso, come un'euristica greedy
  3. Risolve il rilassamento lineare e arrotonda la soluzione
  4. 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).
dp-f-042 · livello facile · dispensa
Nella programmazione dinamica (PD) i sottoproblemi generati dalla scomposizione sono «indipendenti». Che cosa significa?
  1. Ciascuno compare una sola volta nella ricorsione
  2. Hanno tutti la stessa dimensione
  3. Le loro soluzioni ottime non hanno elementi in comune
  4. 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.
dp-f-043 · livello facile · dispensa
In programmazione dinamica (PD), che cosa afferma la proprietà di sottostruttura ottima di una scomposizione ricorsiva?
  1. Ogni soluzione ottima di un sottoproblema è ottima anche per il problema
  2. I sottoproblemi si ripetono molte volte nella ricorsione
  3. Una soluzione ottima del problema si ottiene combinando soluzioni ottime dei suoi sottoproblemi
  4. 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.
dp-f-044 · livello facile · dispensa
Quale è il primo passo nel progetto di un algoritmo di programmazione dinamica (PD)?
  1. Calcolare un upper bound con un'euristica
  2. Individuare la scomposizione ricorsiva in sottoproblemi e verificare sottostruttura ottima e sottoproblemi sovrapposti
  3. Scrivere il modello di programmazione lineare intera e il suo rilassamento
  4. 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.
dp-f-045 · livello facile · dispensa
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?
  1. Un ordine dei sottoproblemi in cui ognuno viene dopo quelli da cui dipende
  2. Che i sottoproblemi non si ripetano mai
  3. Che la tabella sia riempita in ordine casuale
  4. 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.
dp-f-046 · livello facile · dispensa
Fra gli algoritmi di programmazione dinamica del modulo, quale ha un numero di passi polinomiale nella dimensione dell'input (e non solo pseudo-polinomiale)?
  1. La PD per lo zaino 0-1, $\Theta(nc)$
  2. La PD per lo zaino limitato, $\Theta(nc\,b_{\max})$
  3. La PD per il lot sizing con capacità, $O(mDC)$
  4. 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.
dp-f-047 · livello facile · dispensa
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?
  1. Mai, perché il vettore rende il problema fortemente polinomiale
  2. Solo quando tutte le capacità sono uguali
  3. Solo per un numero $m$ fissato di dimensioni o di zaini
  4. 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$.
dp-f-048 · livello facile · dispensa
In un algoritmo di programmazione dinamica (PD), che cosa contiene la lookup table?
  1. I sottoproblemi ancora da risolvere, in ordine di priorità
  2. Il valore ottimo di ogni sottoproblema già risolto, letto quando il sottoproblema ricompare
  3. L'elenco di tutte le soluzioni ammissibili del problema
  4. 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.
dp-f-191 · livello ipotesi · dispensa
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?
  1. La PD diventa polinomiale
  2. La tabella ha meno celle
  3. Combinare i valori ottimi dei sottoproblemi può dare una soluzione non ottima, e la ricorrenza non è corretta
  4. 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.
dp-f-192 · livello facile · dispensa
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?
  1. Lot sizing senza capacità e zaino con setup
  2. Zaino multidimensionale e zaini multipli, con uno stato per ogni vettore di capacità
  3. Zaino 0/1 e subset sum
  4. 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.
dp-f-193 · livello teorema · dispensa
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?
  1. I sottoproblemi si ripetono, e la PD risolve ciascuno una volta sola memorizzandone il valore nella tabella
  2. Perché la PD esamina meno soluzioni ammissibili per ogni sottoproblema
  3. Perché la PD usa una ricorrenza diversa
  4. 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.
dp-f-194 · livello facile · dispensa
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)?
  1. La PD diventa scorretta
  2. La PD diventa polinomiale
  3. La tabella ha più celle dei sottoproblemi
  4. 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.
dp-f-195 · livello facile · dispensa
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?
  1. Dal sottoproblema più grande al più piccolo
  2. Solo lungo la diagonale
  3. In un ordine in cui ogni sottoproblema viene dopo tutti quelli da cui dipende
  4. 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.
dp-f-196 · livello facile · dispensa
Fra gli algoritmi di programmazione dinamica del modulo, quali hanno un numero di passi polinomiale nella dimensione dell'istanza, e non solo pseudo-polinomiale?
  1. Tutti
  2. Wagner-Whitin per il lot sizing senza capacità ($\Theta(m^2)$) e il taglio delle aste ($\Theta(n^2)$)
  3. La PD dello zaino 0/1 e quella del subset sum
  4. 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à.
dp-f-250 · livello teorema · dispensa
Un problema ha la sottostruttura ottima e i sottoproblemi sovrapposti. Che cosa garantisce un algoritmo di programmazione dinamica (PD) basato su una ricorrenza corretta?
  1. Una soluzione ottima in tempo polinomiale nell'input
  2. Una soluzione con rapporto di approssimazione garantito
  3. Ogni sottoproblema risolto tante volte quante compare
  4. 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.
dp-f-251 · livello ipotesi · dispensa
In programmazione dinamica (PD), quale proprietà del problema rende corretta la ricorrenza, cioè fa sì che dia il valore ottimo?
  1. I dati interi e positivi
  2. Un numero polinomiale di sottoproblemi
  3. La sottostruttura ottima
  4. 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.
dp-f-252 · livello ipotesi · dispensa
In programmazione dinamica (PD), quale proprietà rende conveniente memorizzare i valori dei sottoproblemi in una tabella?
  1. L'unicità della soluzione ottima
  2. I sottoproblemi sovrapposti
  3. La sottostruttura ottima
  4. La linearità dell'obiettivo
Spiegazione. Se uno stesso sottoproblema compare più volte nella ricorsione, la tabella evita di ricalcolarlo.
dp-f-253 · livello ipotesi · dispensa
Nell'approccio bottom-up della programmazione dinamica, quale condizione deve rispettare l'ordine in cui si riempie la tabella?
  1. Ogni valore viene dopo i valori da cui dipende
  2. I valori vanno in ordine decrescente
  3. I casi base si calcolano per ultimi
  4. Nessuna: l'ordine è indifferente
Spiegazione. La ricorrenza usa valori di sottoproblemi più piccoli: devono essere già nella tabella quando servono.
dp-f-254 · livello teorema · dispensa
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?
  1. $O(S+d)$
  2. $O(S^{d})$
  3. $O(d^{S})$
  4. $O(S\,d)$
Spiegazione. Ogni sottoproblema si calcola una volta, con $O(d)$ passi: in tutto $O(S\,d)$.
dp-f-255 · livello teorema · dispensa
Che cosa distingue la programmazione dinamica (PD) dal semplice approccio ricorsivo «dividi e conquista»?
  1. La PD trova solo soluzioni approssimate
  2. La PD non usa ricorrenze né casi base
  3. La PD memorizza i valori e non li ricalcola
  4. La PD usa sottoproblemi di tipo diverso
Spiegazione. Entrambi dividono in sottoproblemi dello stesso tipo; la PD salva i valori in una tabella e risolve ogni sottoproblema una volta sola.
dp-f-256 · livello ipotesi · dispensa
Nel progetto di un algoritmo di PD, a che cosa servono i casi base della ricorrenza?
  1. Eliminano i sottoproblemi sovrapposti
  2. Danno i valori dei sottoproblemi più piccoli, da cui partono tutti gli altri
  3. Danno direttamente la soluzione ottima del problema
  4. Servono solo nell'approccio top-down
Spiegazione. Senza casi base la ricorrenza non si chiude: i loro valori sono noti senza ricorsione e da essi si calcolano tutti gli altri.
dp-f-257 · livello teorema · dispensa
In un algoritmo di PD il valore ottimo si calcola con la ricorrenza (passo 1). Come si ottiene una soluzione ottima (passo 2)?
  1. Si memorizza la scelta fatta in ogni cella e si ripercorre all'indietro
  2. Si risolve di nuovo il problema con un solver PLI
  3. Si prende la cella di valore massimo di ogni riga
  4. 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.
dp-f-299 · livello facile · dispensa
Che tipo di algoritmo è un algoritmo di programmazione dinamica (PD)?
  1. Un algoritmo di approssimazione
  2. Un metodo di ricerca locale
  3. Un algoritmo esatto
  4. Un'euristica senza garanzia
Spiegazione. La PD combina le soluzioni ottime dei sottoproblemi e trova una soluzione ottima: è un algoritmo esatto.
dp-f-300 · livello facile · dispensa
Nell'approccio top-down con memoizzazione, che cosa fa una chiamata ricorsiva su un sottoproblema già risolto?
  1. Interrompe l'algoritmo
  2. Restituisce il valore salvato nella tabella
  3. Ricalcola il valore da capo
  4. Restituisce $0$
Spiegazione. La tabella memorizza i valori già calcolati: una seconda chiamata li legge invece di ricalcolarli.
dp-f-301 · livello facile · dispensa
Quale differenza c'è fra l'approccio top-down e l'approccio bottom-up della PD?
  1. Top-down parte dal problema e ricorre; bottom-up riempie la tabella dai casi base
  2. Top-down è esatto, bottom-up è euristico
  3. Bottom-up non usa la ricorrenza
  4. Top-down non usa casi base
Spiegazione. Usano la stessa ricorrenza e danno lo stesso valore; cambia solo l'ordine in cui si calcolano i sottoproblemi.
dp-f-302 · livello facile · dispensa
Che cosa vuol dire che un problema ha la sottostruttura ottima?
  1. Ogni sottoproblema ha una soluzione unica
  2. I sottoproblemi sono indipendenti
  3. Il problema ha pochi sottoproblemi
  4. Una soluzione ottima contiene soluzioni ottime dei suoi sottoproblemi
Spiegazione. È la proprietà che permette di scrivere il valore ottimo con una ricorrenza sui valori ottimi dei sottoproblemi.
dp-f-303 · livello facile · dispensa
Che cosa vuol dire che un problema ha sottoproblemi sovrapposti?
  1. Ogni sottoproblema compare una volta sola
  2. I sottoproblemi sono di tipo diverso
  3. Gli stessi sottoproblemi compaiono più volte nella ricorsione
  4. I sottoproblemi hanno soluzioni comuni
Spiegazione. È ciò che rende utile la tabella: ogni sottoproblema si calcola una volta e poi si riusa.
dp-f-304 · livello facile · dispensa
Negli algoritmi di PD del corso, quali sono i due passi?
  1. Il rilassamento lineare, poi l'arrotondamento
  2. Il valore ottimo con la ricorrenza, poi una soluzione ottima dalla tabella aggiuntiva
  3. Un bound inferiore, poi un bound superiore
  4. Una soluzione euristica, poi la ricerca locale
Spiegazione. Una ricorrenza con i suoi casi base dà il valore ottimo; una tabella aggiuntiva, letta a ritroso, dà una soluzione ottima.
dp-f-305 · livello facile · dispensa
Calcolare i numeri di Fibonacci con la ricorsione semplice $F(n)=F(n-1)+F(n-2)$ richiede un tempo esponenziale. Che cosa cambia con la PD?
  1. Ogni $F(k)$ si calcola una volta: $\Theta(n)$ passi
  2. Nulla: il tempo resta esponenziale
  3. Il tempo diventa $\Theta(\log n)$ senza tabella
  4. Il risultato cambia
Spiegazione. I sottoproblemi $F(k)$ si ripetono molte volte nella ricorsione; con la tabella ciascuno si calcola una volta.

2. PD per il problema dello zaino 0/1 (38)

dp-f-004 · livello facile · dispensa
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$?
  1. Altrimenti $v[k-w_j]$ non sarebbe ancora calcolato, e la ricorrenza leggerebbe celle vuote
  2. Così il numero di passi scende da $\Theta(nc)$ a $\Theta(c)$, perché si salta metà vettore
  3. Così si riempie per prima la cella $v[c]$, che contiene il valore ottimo
  4. 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)$.
dp-f-005 · livello facile · dispensa
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?
  1. $\max\{u(n,q): q\in\{0,\dots,P\}\}$
  2. $u(n,c)$
  3. $\max\{q\in\{0,\dots,P\}: u(n,q)\le c\}$
  4. $\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.
dp-f-006 · livello facile · dispensa
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?
  1. $j$ diminuisce di $1$ e $k$ diminuisce di $p_j$
  2. $j$ diminuisce di $1$ e $k$ diminuisce di $w_j$
  3. $j$ diminuisce di $1$ e $k$ resta uguale
  4. $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)$).
dp-f-049 · livello facile · dispensa
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$?
  1. $40$
  2. $16$
  3. $50$
  4. $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.
dp-f-050 · livello facile · dispensa
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$?
  1. $5$
  2. $3$
  3. $4$
  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.
dp-f-051 · livello facile · dispensa
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?
  1. Gli stati non dominati hanno pesi tutti diversi, e i pesi interi possibili sono $0,1,\dots,c$
  2. Ogni oggetto aggiunge al più uno stato alla lista
  3. Gli stati non dominati hanno profitti tutti uguali
  4. 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\}$.
dp-f-052 · livello facile · dispensa
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'$?
  1. Perché $(w',p')$ non è ammissibile
  2. Perché gli stati dominati hanno sempre peso maggiore della capacità
  3. Perché la lista deve avere al più $n$ elementi
  4. 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.
dp-f-053 · livello facile · dispensa
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)$?
  1. $50$
  2. $140$
  3. $145$
  4. $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à.
dp-f-054 · livello facile · dispensa
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)$?
  1. $8$
  2. $7$
  3. $+\infty$
  4. $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.
dp-f-055 · livello facile · dispensa
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?
  1. $6$
  2. $8$
  3. $5$
  4. $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$.
dp-f-056 · livello facile · dispensa
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$?
  1. A ogni passo: gli stati di peso maggiore di $c$ si scartano subito
  2. All'inizio: si scartano gli oggetti di peso maggiore di $c/2$
  3. Mai: il valore ottimo è il profitto massimo in $L_n$
  4. 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$.
dp-f-057 · livello facile · dispensa
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?
  1. $14$
  2. $11$
  3. $15$
  4. $19$
Spiegazione. Fra gli stati di peso al più $9$ il profitto massimo è $15$, dello stato $(9,15)$. $(11,19)$ supera la capacità.
dp-f-157 · livello facile · dispensa
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$)?
  1. $4$
  2. $5$
  3. $6$
  4. $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.
dp-f-158 · livello facile · dispensa
Zaino 0/1 con capacità $c=5$, profitti $p=(6,7,8)$ e pesi $w=(2,3,3)$. Quanto vale il valore ottimo, trovato enumerando i sottoinsiemi?
  1. $21$
  2. $14$
  3. $15$
  4. $13$
Spiegazione. $\{1,3\}$ pesa $5$ e vale $14$; $\{1,2\}$ vale $13$; $\{2,3\}$ varrebbe $15$ ma pesa $6>5$; $21$ è la somma di tutti i profitti.
dp-f-159 · livello facile · dispensa
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)$?
  1. La soluzione $\{1,3\}$, di peso $5\le c$ e profitto $14$
  2. La soluzione $\{2\}$, di peso $3$ e profitto $7$
  3. Una soluzione inammissibile di peso $8$
  4. 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.
dp-f-160 · livello teorema · dispensa
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)?
  1. Entrambi crescono di $1000$ volte
  2. I passi non cambiano, perché la soluzione ottima è la stessa
  3. I passi crescono di circa $10$ volte
  4. 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.
dp-f-161 · livello facile · dispensa
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?
  1. Il vettore richiede $\Theta(nc^2)$ passi
  2. Identici anche in memoria
  3. Stesso numero di passi $\Theta(nc)$; il vettore usa memoria $\Theta(c)$ invece di $\Theta(nc)$
  4. 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.
dp-f-162 · livello facile · dispensa
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$?
  1. $300$
  2. $8$, perché $|L_j|\le\min\{2^j,c+1\}$
  3. $101$
  4. $3$
Spiegazione. Con tre oggetti ci sono $2^3=8$ sottoinsiemi, quindi al più $8$ stati, molto meno delle $101$ capacità della matrice.
dp-f-163 · livello teorema · dispensa
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)$?
  1. Quando i profitti sono piccoli e la capacità è grande ($P\ll c$)
  2. Quando la capacità è piccola e i profitti grandi
  3. Sempre, perché $\Theta(nP)$ è polinomiale
  4. 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.
dp-f-164 · livello facile · dispensa
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?
  1. Perché le liste ignorano gli oggetti di peso grande
  2. Perché le liste memorizzano solo l'ultima riga
  3. Non lo è: hanno sempre $(n+1)(P+1)$ elementi
  4. 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.
dp-f-197 · livello facile · dispensa
Zaino 0/1 con $n$ oggetti: quanti sottoinsiemi di oggetti ci sono, e quanti di essi la PD considera esplicitamente?
  1. $n!$ sottoinsiemi; la PD ne considera $n^2$
  2. $n^2$ sottoinsiemi; la PD li considera tutti
  3. $2^n$ sottoinsiemi; la PD non li enumera, ma calcola $(n+1)(c+1)$ valori $v(j,k)$
  4. $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.
dp-f-198 · livello facile · dispensa
Nello zaino 0/1 con $c=5$, $p=(6,7,8)$ e $w=(2,3,3)$, quali vettori binari $(x_1,x_2,x_3)$ sono inammissibili?
  1. $(0,1,1)$, $(1,1,0)$ e $(1,1,1)$
  2. $(0,1,1)$ e $(1,1,1)$
  3. $(1,1,0)$ e $(1,0,1)$
  4. Solo $(1,1,1)$
Spiegazione. $(0,1,1)$ pesa $6$ e $(1,1,1)$ pesa $8$, entrambi oltre $c=5$; $(1,1,0)$ e $(1,0,1)$ pesano esattamente $5$.
dp-f-199 · livello facile · dispensa
Nello zaino 0/1 una soluzione si codifica con un vettore binario $(x_1,\dots,x_n)$. Quali due quantità lineari si calcolano dal vettore?
  1. Il peso $\sum_jw_jx_j$, da confrontare con $c$, e il profitto $\sum_jp_jx_j$, da massimizzare
  2. Il numero di oggetti $\sum_jx_j$ e il peso massimo
  3. Il profitto medio e il peso medio
  4. Il prodotto dei pesi e il prodotto dei profitti
Spiegazione. Ammissibilità e valore sono due somme pesate del vettore: è ciò che rende lo zaino un problema di PLI con un solo vincolo.
dp-f-200 · livello facile · dispensa
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?
  1. $86$; $\Theta(n+c)$
  2. $60$; $\Theta(nc)$
  3. $96$; $\Theta(n^2c)$
  4. $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$.
dp-f-201 · livello facile · dispensa
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?
  1. Perché Merge ordina le liste in $\Theta(c\log c)$
  2. Perché le liste ignorano la capacità
  3. Ogni lista ha al più $c+1$ stati (pesi distinti in $\{0,\dots,c\}$), e Merge li scandisce una volta per oggetto
  4. 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.
dp-f-202 · livello facile · dispensa
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)$?
  1. $8$
  2. $24$, cioè $(n+1)(c+1)$
  3. $11$
  4. $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.
dp-f-203 · livello facile · dispensa
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$?
  1. $365$
  2. $252$
  3. $86$
  4. $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$.
dp-f-204 · livello facile · dispensa
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?
  1. $\Theta(nP)$, come la matrice
  2. $\Theta(c)$
  3. $\Theta(n)$
  4. $\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.
dp-f-205 · livello facile · dispensa
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?
  1. $2$
  2. $21$
  3. $4$, perché $|L_j|\le\min\{2^j,P+1\}$
  4. $22$
Spiegazione. Due oggetti danno $2^2=4$ sottoinsiemi, quindi al più $4$ profitti diversi, molti meno delle $P+1=22$ colonne della matrice.
dp-f-206 · livello facile · dispensa
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)$?
  1. $84$
  2. $88$
  3. $63$
  4. $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$.
dp-f-207 · livello teorema · dispensa
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?
  1. 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$
  2. La seconda PD ignora i pesi
  3. Nella seconda le liste sono ordinate per peso
  4. 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.
dp-f-258 · livello ipotesi · dispensa
La PD per lo zaino 0/1 (KP) usa i valori $v(j,k)$ per le capacità $k=0,1,\dots,c$. Quale ipotesi sui dati serve?
  1. Pesi $w_j$ tutti diversi
  2. Pesi $w_j$ e capacità $c$ interi
  3. Profitti $p_j$ interi
  4. Oggetti ordinati per efficienza
Spiegazione. Gli indici $k$ sono le capacità residue $0,1,\dots,c$: servono pesi e capacità interi; i profitti possono essere qualunque.
dp-f-259 · livello teorema · dispensa
La PD per lo zaino 0/1 esegue $\Theta(nc)$ passi. Perché questo tempo non è polinomiale nella dimensione dell'input?
  1. $c$ si scrive con $O(\log c)$ bit e il tempo cresce con il valore $c$
  2. Perché la tabella ha $2^n$ celle
  3. Perché ogni cella richiede $\Theta(n)$ confronti
  4. Perché $n$ non è noto a priori
Spiegazione. Un tempo proporzionale al valore $c$ è esponenziale nella sua lunghezza in bit: è pseudo-polinomiale.
dp-f-260 · livello teorema · dispensa
Nella PD per lo zaino 0/1 con un solo vettore di $c+1$ celle, le capacità $k$ si scorrono dall'alto verso il basso. Perché?
  1. Così si dimezzano i confronti
  2. Così l'oggetto $j$ si può usare più volte
  3. Perché le capacità piccole non servono
  4. Così $v(k-w_j)$ è ancora il valore senza l'oggetto $j$
Spiegazione. La cella $k-w_j$ non è ancora aggiornata: l'oggetto $j$ si usa al più una volta. Scorrendo verso l'alto si avrebbe lo zaino illimitato.
dp-f-261 · livello ipotesi · dispensa
Il secondo algoritmo di PD per lo zaino 0/1 calcola $u(j,q)$, il peso minimo per ottenere esattamente il profitto $q$. Quale ipotesi sui dati serve?
  1. Capacità $c$ pari
  2. Profitti $p_j$ tutti diversi
  3. Profitti $p_j$ interi
  4. Pesi $w_j$ interi
Spiegazione. Gli indici $q$ sono i profitti $0,1,\dots,P$: servono profitti interi; i pesi possono essere qualunque.
dp-f-262 · livello teorema · dispensa
Nella PD sui profitti per lo zaino 0/1, $u(n,q)$ è il peso minimo per ottenere il profitto $q$. Come si legge il valore ottimo con capacità $c$?
  1. Il più grande $u(n,q)$
  2. Il più grande $q$ con $u(n,q)\le c$
  3. Il più piccolo $q$ con $u(n,q)\ge c$
  4. Il valore $u(n,P)$
Spiegazione. Il profitto $q$ si ottiene senza superare la capacità se e solo se $u(n,q)\le c$: il valore ottimo è il più grande di questi $q$.
dp-f-263 · livello teorema · dispensa
Per lo zaino 0/1 con capacità $c$ e profitto totale $P$ ci sono una PD in $\Theta(nc)$ e una sui profitti in $\Theta(nP)$. Quando conviene la seconda?
  1. Quando $P<c$
  2. Quando $c<P$
  3. Quando i pesi valgono $1$
  4. Mai
Spiegazione. I due tempi differiscono solo per il fattore $c$ o $P$: con profitti piccoli conviene la PD sui profitti.
dp-f-264 · livello ipotesi · dispensa
Nell'implementazione con liste della PD per lo zaino 0/1 si scarta uno stato (peso $W$, profitto $Q$) dominato da $(W',Q')$. Quando c'è dominanza?
  1. $W'\ge W$ e $Q'\ge Q$
  2. $W'+Q'\ge W+Q$
  3. $W'\le W$ e $Q'\le Q$
  4. $W'\le W$ e $Q'\ge Q$, con almeno una disuguaglianza stretta
Spiegazione. Uno stato che pesa di più e rende non di più non porta mai a una soluzione migliore.

3. PD per il problema dello zaino illimitato (25)

dp-f-007 · livello facile · dispensa
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$?
  1. $p_j+v(j-1,k)$, che non riduce la capacità
  2. $v(j-1,k)$, che esclude il tipo $j$
  3. $p_j+v(j,k-w_j)$, che resta nella riga $j$
  4. $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.
dp-f-008 · livello facile · dispensa
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$?
  1. $v(k-1)$: si usa la capacità precedente
  2. $0$: parte della capacità può restare inutilizzata
  3. $-\infty$: la capacità va riempita esattamente
  4. $+\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.
dp-f-009 · livello facile · dispensa
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?
  1. $c+1$ celle, $\Theta(nc)$ passi
  2. $c$ celle, $\Theta(c)$ passi
  3. $(n+1)(c+1)$ celle, $\Theta(nc)$ passi
  4. $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.
dp-f-058 · livello facile · dispensa
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à?
  1. $27$
  2. $8$
  3. $60$
  4. $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à.
dp-f-059 · livello facile · dispensa
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)$?
  1. $8$
  2. $12$
  3. $11$
  4. $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$.
dp-f-060 · livello facile · dispensa
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$?
  1. Si legge $s(c)$: tutte le copie sono di quel tipo
  2. Si prende una copia del tipo $s(k)$ e si pone $k\leftarrow k-w_{s(k)}$, finché nessun tipo entra
  3. Si prende il tipo $s(k)$ e si passa al tipo successivo, come nel KP
  4. 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.
dp-f-061 · livello facile · dispensa
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?
  1. Riga per riga ($j$ crescente) e, in ogni riga, per $k$ crescente
  2. Riga per riga e, in ogni riga, per $k$ decrescente
  3. Colonna per colonna, per $j$ decrescente
  4. 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$.
dp-f-062 · livello facile · dispensa
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)$?
  1. $11$
  2. $3$
  3. $10$
  4. $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.
dp-f-063 · livello facile · dispensa
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?
  1. La prima esegue $\Theta(nc)$ passi, la seconda $\Theta(n^2c)$
  2. Hanno lo stesso numero di celle, ma la seconda è esponenziale
  3. La prima ha $c+1$ celle, la seconda $(n+1)(c+1)$; entrambe eseguono $\Theta(nc)$ passi
  4. 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.
dp-f-064 · livello facile · dispensa
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$?
  1. Perché $-\infty$ non si può memorizzare in una tabella
  2. Lo zaino non deve essere riempito: senza tipi disponibili la soluzione vuota è ammissibile e vale $0$
  3. Perché i profitti sono positivi, quindi nessun valore è negativo
  4. 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$.
dp-f-065 · livello facile · dispensa
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?
  1. Le celle $v(k-w_j)$, una per ogni tipo $j$ con $w_j\le k$
  2. Solo la cella $v(k-1)$
  3. Tutte le celle $v(0),\dots,v(k-1)$
  4. 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.
dp-f-066 · livello facile · dispensa
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?
  1. Niente: con copie illimitate nessun tipo è dominato
  2. Usarlo solo per riempire la capacità residua
  3. Eliminare invece il tipo $i$, che ha peso minore
  4. 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$.
dp-f-165 · livello facile · dispensa
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?
  1. $x_1\le3$ e $x_2\le2$, cioè $x_j\le\lfloor c/w_j\rfloor$
  2. $x_j\le1$
  3. $x_1\le10$ e $x_2\le10$
  4. $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.
dp-f-166 · livello facile · dispensa
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?
  1. Perché si considera al più una copia per tipo
  2. Perché la capacità si riduce a $\lfloor c/n\rfloor$
  3. Le copie fanno crescere i passi a $\Theta(nc^2)$
  4. 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})$).
dp-f-208 · livello facile · dispensa
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?
  1. $121$
  2. $12$
  3. $6$
  4. $4$
Spiegazione. $\lfloor10/4\rfloor=2$ e $\lfloor10/3\rfloor=3$: $(2+1)(3+1)=12$ candidate, di cui solo alcune rispettano la capacità.
dp-f-209 · livello facile · dispensa
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?
  1. $(2,1)$, peso $10$, profitto $17$
  2. $(3,1)$, peso $13$, profitto $22$
  3. $(1,2)$, peso $11$, profitto $19$
  4. $(0,3)$, peso $12$, profitto $21$
Spiegazione. $2\cdot3+1\cdot4=10\le c$ e $2\cdot5+7=17$; gli altri superano la capacità.
dp-f-210 · livello facile · dispensa
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?
  1. Perché nell'UKP si prende al più una copia
  2. Perché le copie hanno pesi diversi
  3. Perché la capacità è illimitata
  4. 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.
dp-f-211 · livello facile · dispensa
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?
  1. Circa $2^{10}$; esponenziale
  2. Circa $12$; $\Theta(n+c)$
  3. Circa $20$; $\Theta(nc)$
  4. 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ù.
dp-f-212 · livello facile · dispensa
La prima PD per lo zaino illimitato usa un solo vettore $v(0),\dots,v(c)$. Quale ricorrenza calcola, con $v(0)=0$?
  1. $v(k)=\min_j\{w_j+v(k-p_j)\}$
  2. $v(k)=\max\{v(k-1),\ \max_{j:\,w_j\le k}\{p_j+v(k-w_j)\}\}$
  3. $v(k)=\max_j\{p_j+v(k-w_j)\}$ con al più una copia per tipo
  4. $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.
dp-f-213 · livello facile · dispensa
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?
  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
  2. Si usano le righe in ordine inverso
  3. Il numero di passi diventa $\Theta(nc^2)$
  4. 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.
dp-f-214 · livello facile · dispensa
Le PD dello zaino illimitato eseguono $\Theta(nc)$ passi. Se la capacità passa da $c$ a $10c$ (con gli stessi tipi), come cambia il numero di passi?
  1. Resta uguale
  2. Diventa $100$ volte più grande
  3. Cresce di un solo passo
  4. Diventa circa $10$ volte più grande
Spiegazione. Il numero di passi è lineare nel valore di $c$: è pseudo-polinomiale, perché scrivere $10c$ richiede solo pochi bit in più.
dp-f-265 · livello ipotesi · dispensa
Nello zaino illimitato (UKP) la PD usa un solo indice: $v(k)=\max_{j:\,w_j\le k}\{p_j+v(k-w_j)\}$. Quale caratteristica del problema lo permette?
  1. Copie illimitate di ogni tipo
  2. Pesi ordinati in modo crescente
  3. Al più una copia per tipo
  4. Capacità da riempire esattamente
Spiegazione. Con copie illimitate le scelte possibili dipendono solo dalla capacità residua, non dagli oggetti già usati.
dp-f-266 · livello ipotesi · dispensa
Nella PD per lo zaino illimitato, quando nessun tipo entra nella capacità residua $k$ si pone $v(k)=0$ e non $-\infty$. Su quale ipotesi si basa?
  1. I profitti sono positivi
  2. I pesi superano $c$
  3. Ogni tipo compare almeno una volta
  4. La capacità può restare inutilizzata
Spiegazione. Una soluzione non deve riempire lo zaino: senza oggetti vale $0$; $-\infty$ indicherebbe un sottoproblema senza soluzioni.
dp-f-267 · livello teorema · dispensa
Il secondo algoritmo di PD per lo zaino illimitato usa $v(j,k)=\max\{v(j-1,k),\,p_j+v(j,k-w_j)\}$. Perché il secondo termine sta nella riga $j$?
  1. Per usare il tipo $j$ una volta sola
  2. Perché $v$ non dipende da $j$
  3. Dopo una copia del tipo $j$ se ne possono prendere altre
  4. La riga $j-1$ non è ancora calcolata
Spiegazione. Restare nella riga $j$ lascia disponibile il tipo $j$: è la differenza con lo zaino 0/1.
dp-f-268 · livello teorema · dispensa
Quanti passi esegue la PD $v(k)=\max_{j:\,w_j\le k}\{p_j+v(k-w_j)\}$ per lo zaino illimitato con $n$ tipi e capacità $c$, e di che tipo è il tempo?
  1. $\Theta(2^n c)$, esponenziale
  2. $\Theta(nc)$, pseudo-polinomiale
  3. $\Theta(nc)$, polinomiale
  4. $\Theta(c^2)$, pseudo-polinomiale
Spiegazione. Per ognuna delle $c+1$ capacità si guardano $n$ tipi: $\Theta(nc)$, polinomiale nel valore $c$ ma non nella sua lunghezza.

4. PD per il problema dello zaino limitato (22)

dp-f-010 · livello facile · dispensa
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?
  1. $11$ ($d=0,\dots,10$)
  2. $3$ ($d=0,1,2$)
  3. $4$ ($d=0,1,2,3$)
  4. $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à.
dp-f-011 · livello facile · dispensa
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?
  1. Generalizza il KP ($b_j=1$) e l'UKP ($b_j=\lfloor c/w_j\rfloor$); la PD esegue $\Theta(nc\,b_{\max})$ passi
  2. Generalizza il KP ($b_j=1$) ma non l'UKP; la PD esegue $\Theta(nc\,b_{\max})$ passi
  3. Generalizza il KP ($b_j=1$) e l'UKP ($b_j=\lfloor c/w_j\rfloor$); la PD esegue $\Theta(nc)$ passi
  4. È 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.
dp-f-012 · livello facile · dispensa
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?
  1. $k\leftarrow k-s[j][k]$, e $j$ diminuisce di $1$
  2. $k\leftarrow k-w_j$, e $j$ resta uguale
  3. $k$ resta uguale, e $j$ diminuisce di $s[j][k]$
  4. $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.
dp-f-067 · livello facile · dispensa
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à?
  1. $144$
  2. $64$
  3. $8$
  4. $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.
dp-f-068 · livello facile · dispensa
Nello zaino limitato (BKP: profitti $p_j$, pesi $w_j$, copie disponibili $b_j$, capacità $c$), come si codifica una soluzione ammissibile?
  1. Con un sottoinsieme degli oggetti di peso totale al più $c$
  2. Con un vettore intero $x\ge 0$ tale che $\sum_j w_jx_j=c$
  3. Con un vettore binario $x$ tale che $\sum_j b_jw_jx_j\le c$
  4. 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$).
dp-f-069 · livello facile · dispensa
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)$?
  1. $11$
  2. $16$
  3. $15$
  4. $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$.
dp-f-070 · livello facile · dispensa
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)$?
  1. $n$, uno per ogni tipo di oggetto
  2. $\min\{b_j,\lfloor k/w_j\rfloor\}+1$, uno per ogni numero di copie del tipo $j$
  3. $2$, come nel KP
  4. $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.
dp-f-071 · livello facile · dispensa
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)$?
  1. È non decrescente in $k$: con più capacità le soluzioni ammissibili sono di più
  2. È crescente in $k$ in senso stretto
  3. È costante: il profitto non dipende dalla capacità
  4. 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.
dp-f-072 · livello facile · dispensa
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$?
  1. $-\infty$ per $k\ge 1$
  2. $k$ per ogni $k$
  3. $+\infty$ per $k\ge 1$
  4. $0$ per ogni $k$
Spiegazione. Senza tipi disponibili l'unica soluzione è lo zaino vuoto, ammissibile per ogni capacità e di profitto $0$.
dp-f-073 · livello facile · dispensa
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$?
  1. $\Theta(2^{\sum_j b_j})$, esponenziale
  2. $\Theta(c\,b_{\max})$, indipendente da $n$
  3. $\Theta(c\sum_j b_j)$, al più $\Theta(nc\,b_{\max})$ come la PD diretta
  4. $\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.
dp-f-074 · livello facile · dispensa
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?
  1. Quando $b_jw_j<c$
  2. Quando $b_j\ge\lfloor c/w_j\rfloor$: più copie non entrerebbero comunque
  3. Quando $b_j=1$
  4. 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.
dp-f-075 · livello facile · dispensa
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?
  1. Alla PD dello zaino 0-1: $v(j,k)=\max\{v(j-1,k),\ p_j+v(j-1,k-w_j)\}$
  2. Alla PD dello zaino illimitato: $v(j,k)=\max\{v(j-1,k),\ p_j+v(j,k-w_j)\}$
  3. Alla PD del subset sum, con valori booleani
  4. 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.
dp-f-167 · livello facile · dispensa
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à)?
  1. $30$
  2. $128$
  3. $7$
  4. $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.
dp-f-168 · livello ipotesi · dispensa
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à?
  1. Perché nel BKP vale sempre $b_j=1$
  2. Perché la PD ignora i tipi con $b_j>c$
  3. Non si può: $b_{\max}$ può superare $c$ e il bound cresce
  4. 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)$.
dp-f-215 · livello facile · dispensa
Zaino limitato con $c=12$, pesi $w=(5,3,2)$ e limiti $b=(1,2,4)$ sulle copie. Quale vettore $(x_1,x_2,x_3)$ è una soluzione ammissibile?
  1. $(1,1,2)$
  2. $(0,2,4)$
  3. $(1,3,0)$
  4. $(2,0,1)$
Spiegazione. $(1,1,2)$ pesa $5+3+4=12$ e rispetta i limiti. $(0,2,4)$ pesa $14$; $(1,3,0)$ supera $b_2=2$; $(2,0,1)$ supera $b_1=1$.
dp-f-216 · livello facile · dispensa
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?
  1. $3$
  2. $8$
  3. $30$
  4. $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.
dp-f-217 · livello facile · dispensa
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?
  1. $3$
  2. $8$
  3. $4$
  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})$.
dp-f-218 · livello facile · dispensa
La PD per lo zaino limitato esegue nel caso peggiore $S=3n(c+1)(b_{\max}+1)+3n(c+1)+n+2c+4$ passi. Quanti sono per $n=2$, $c=4$ e $b_{\max}=2$?
  1. $44$
  2. $134$
  3. $90$
  4. $120$
Spiegazione. $3\cdot2\cdot5\cdot3=90$, $3\cdot2\cdot5=30$, poi $2+8+4$: in tutto $134$. $90$ è solo il termine dominante.
dp-f-269 · livello teorema · dispensa
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?
  1. $\Theta(n\,b_{\max})$
  2. $\Theta(c\,b_{\max}^{\,n})$
  3. $\Theta(nc\,b_{\max})$
  4. $\Theta(nc)$
Spiegazione. $(n+1)(c+1)$ celle, ciascuna con fino a $b_{\max}+1$ confronti.
dp-f-270 · livello ipotesi · dispensa
Nello zaino limitato si può sostituire $b_j$ con $\min\{b_j,\lfloor c/w_j\rfloor\}$. Perché il problema non cambia?
  1. Tutti i $b_j$ diventano $1$
  2. Più di $\lfloor c/w_j\rfloor$ copie non entrano comunque
  3. L'ottimo usa meno di $b_j/2$ copie
  4. I tipi con $b_j>c$ si eliminano
Spiegazione. Ogni copia pesa $w_j$: con capacità $c$ ne entrano al più $\lfloor c/w_j\rfloor$; in più si ottiene $b_{\max}\le c$.
dp-f-271 · livello teorema · dispensa
Lo zaino limitato (BKP), con al più $b_j$ copie del tipo $j$, generalizza quali problemi?
  1. Lo zaino 0/1 ($b_j=1$) e lo zaino illimitato ($b_j=\lfloor c/w_j\rfloor$)
  2. Lo zaino 0/1 ($b_j=0$) e il subset sum ($b_j=1$)
  3. Lo zaino illimitato ($b_j=1$) e lo zaino 0/1 ($b_j=c$)
  4. Il cambio monete ($b_j=1$) e lo zaino 0/1 ($b_j=c$)
Spiegazione. Una copia per tipo dà lo zaino 0/1; tutte le copie che entrano danno lo zaino illimitato.
dp-f-272 · livello ipotesi · dispensa
Nella ricorrenza $v(j,k)=\max_{d}\{d\,p_j+v(j-1,k-d\,w_j)\}$ dello zaino limitato, quali valori assume il numero $d$ di copie?
  1. $0,1,\dots,b_j$, qualunque sia $k$
  2. $1,2,\dots,\lfloor c/w_j\rfloor$
  3. Solo $0$ oppure $b_j$
  4. $0,1,\dots,\min\{b_j,\lfloor k/w_j\rfloor\}$
Spiegazione. Al più $b_j$ copie, e devono entrare nella capacità residua: $d\,w_j\le k$.

5. PD per il problema del subset sum (18)

dp-f-013 · livello facile · dispensa
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?
  1. $r(j,0)=\textit{true}$ per ogni $j$, e $r(0,k)=\textit{false}$ per $k\ge 1$
  2. $r(j,0)=\textit{false}$ per ogni $j$, e $r(0,k)=\textit{true}$ per $k\ge 1$
  3. $r(0,k)=\textit{true}$ per ogni $k$
  4. $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.
dp-f-014 · livello facile · dispensa
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?
  1. Nella cella $r(c,n)$
  2. In una qualsiasi cella vera della colonna $c$
  3. Nell'ultima cella vera della riga $n$
  4. 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.
dp-f-015 · livello facile · dispensa
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)$?
  1. $\Theta(2^n)$
  2. $\Theta(n\log c)$
  3. $\Theta(nc)$
  4. $\Theta(c^2)$
Spiegazione. La tabella ha $(n+1)(c+1)$ celle, ciascuna calcolata in tempo costante: $\Theta(nc)$, un tempo pseudo-polinomiale.
dp-f-076 · livello facile · dispensa
Subset sum: pesi $w=(3,5,7)$, obiettivo $c=10$. $r(j,k)$ è vero se un sottoinsieme dei primi $j$ pesi ha somma esattamente $k$. Quanto vale $r(3,10)$?
  1. Falso, perché $10$ non è un peso
  2. Vero, per esempio $3+7$
  3. Falso: nessun sottoinsieme ha somma $10$
  4. Vero, perché $10\le 3+5+7$
Spiegazione. Le somme raggiungibili sono $0,3,5,7,8,10,12,15$: $10=3+7$. Che $c$ sia minore della somma totale non basta: serve una somma esatta.
dp-f-077 · livello facile · dispensa
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)$?
  1. Falso: le somme raggiungibili sono $0,2,4,6$
  2. Vero: $5\le 6$
  3. Vero: $2+2+1$
  4. 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.
dp-f-078 · livello facile · dispensa
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)$?
  1. La scelta di non usare il peso $w_j$
  2. La scelta di usare due volte il peso $w_j$
  3. Il controllo che $k$ non superi l'obiettivo $c$
  4. 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.
dp-f-079 · livello facile · dispensa
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)$?
  1. Se $r(j-1,k)$ è vero si prende $w_j$; altrimenti lo si esclude
  2. Si prende il peso più grande e si ricomincia con $c-w_{\max}$
  3. 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$
  4. 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$.
dp-f-080 · livello facile · dispensa
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?
  1. $13$
  2. $10$
  3. $12$
  4. $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.
dp-f-081 · livello facile · dispensa
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$?
  1. Da $c$ a $w_j$, in modo decrescente, per non usare due volte lo stesso peso
  2. Da $w_j$ a $c$, in modo crescente, per leggere celle già aggiornate
  3. In qualsiasi ordine, perché l'operazione è un «or»
  4. 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.
dp-f-082 · livello facile · dispensa
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$?
  1. $100$
  2. $105$
  3. $32$
  4. $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$.
dp-f-083 · livello facile · dispensa
La PD per il subset sum esegue $\Theta(nc)$ passi con $n$ pesi e obiettivo $c$. Perché il subset sum resta NP-completo?
  1. Perché il numero di sottoinsiemi è $2^n$, e la PD li elenca tutti
  2. Perché la tabella ha valori booleani invece che interi
  3. $c$ si scrive con circa $\log_2 c$ cifre, e $\Theta(nc)$ è esponenziale in quel numero di cifre
  4. 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.
dp-f-084 · livello facile · dispensa
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?
  1. È sì se e solo se $v(n,c)=\sum_j w_j$
  2. È sì se e solo se $v(n,c)=c$
  3. È sì se e solo se $v(n,c)\ge 1$
  4. È 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.
dp-f-169 · livello facile · dispensa
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?
  1. $\Theta(nc)$, come la PD dello zaino 0/1
  2. $\Theta(2^n)$
  3. $\Theta(n\log c)$
  4. $\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.
dp-f-219 · livello facile · dispensa
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?
  1. $44$
  2. $16$
  3. $55$
  4. $40$
Spiegazione. $(4+1)(10+1)=55$ celle, ciascuna calcolata in tempo costante: $\Theta(nc)$.
dp-f-220 · livello facile · dispensa
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?
  1. $\Theta(2^n)$
  2. $\Theta(n)$: un passo per oggetto
  3. $\Theta(nc)$
  4. $\Theta(c)$
Spiegazione. Per ogni oggetto, dall'ultimo al primo, si decide se è stato usato guardando una cella della riga precedente.
dp-f-273 · livello ipotesi · dispensa
Nella PD per il subset sum, $r(j,k)$ dice se $k$ è il peso di un sottoinsieme dei primi $j$ oggetti. Perché $r(j,0)=\textit{true}$ per ogni $j$?
  1. Il sottoinsieme vuoto pesa $0$
  2. I pesi sono positivi
  3. $0$ è il valore obiettivo
  4. Il primo oggetto pesa $0$
Spiegazione. Il valore $0$ si raggiunge sempre senza oggetti; con zero oggetti nessun $k\ge 1$ si raggiunge.
dp-f-274 · livello teorema · dispensa
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ì»?
  1. Se e solo se $z\ge c/2$
  2. Se e solo se $z<c$
  3. Mai: i problemi non sono legati
  4. 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$.
dp-f-275 · livello teorema · dispensa
La PD $r(j,k)=r(j-1,k)\lor r(j-1,k-w_j)$ per il subset sum con $n$ oggetti e valore obiettivo $c$: quanti passi esegue e dove si legge la risposta?
  1. $\Theta(2^n)$; in $r(n,c)$
  2. $\Theta(n+c)$; in $r(n,0)$
  3. $\Theta(nc)$; in $r(n,c)$
  4. $\Theta(nc)$; in $r(c,n)$
Spiegazione. $(n+1)(c+1)$ celle con un «o» logico ciascuna; la risposta riguarda tutti gli oggetti e il valore $c$.

6. PD per il problema dello zaino a scelta multipla (16)

dp-f-016 · livello facile · dispensa
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?
  1. $v(0,k)=0$ per ogni $k$; senza soluzioni ammissibili vale $0$
  2. $v(0,k)=-\infty$ per $k\ge 1$; senza soluzioni ammissibili vale $0$
  3. $v(0,k)=k$ per ogni $k$; senza soluzioni ammissibili vale $+\infty$
  4. $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.
dp-f-017 · livello facile · dispensa
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?
  1. Il caso base $v(0,k)$, perché la prima classe lo sostituisce
  2. Il controllo $w_j\le k$, perché la classe fissa il peso
  3. Il termine $v(h-1,k)$, perché ogni classe dà esattamente un oggetto
  4. 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.
dp-f-018 · livello facile · dispensa
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?
  1. $\Theta(2^q c)$
  2. $\Theta\big(c\sum_{h=1}^{q}|\mathscr{J}_h|\big)=\Theta(nc)$
  3. $\Theta(qc)$
  4. $\Theta(n^q c)$
Spiegazione. Per ogni classe $h$ e ogni capacità $k$ si provano gli oggetti della classe: in tutto $c\sum_h|\mathscr{J}_h|=\Theta(nc)$.
dp-f-121 · livello facile · dispensa
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)$?
  1. $7$
  2. $10$
  3. $9$
  4. $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à.
dp-f-122 · livello facile · dispensa
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$?
  1. Il profitto dell'oggetto più leggero della classe $2$
  2. $v(2,2)=-\infty$: non c'è nessuna soluzione ammissibile
  3. $v(2,2)=0$: non si sceglie nessun oggetto
  4. 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à.
dp-f-123 · livello facile · dispensa
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)$?
  1. $|\mathscr{J}_h|$, uno per ogni oggetto della classe $h$ che entra
  2. $2$, come nel KP 0/1
  3. $|\mathscr{J}_h|+1$, contando la scelta di nessun oggetto
  4. $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.
dp-f-124 · livello facile · dispensa
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)$?
  1. Si sceglie $s(q,c)$ e lo si ripete per ogni classe
  2. Si sceglie in ogni classe l'oggetto di profitto massimo
  3. Si sceglie $j=s(h,k)$ e si pone $h\leftarrow h-1$ senza cambiare $k$
  4. 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.
dp-f-125 · livello facile · dispensa
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$?
  1. $96$
  2. $45$
  3. $64$
  4. $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)$.
dp-f-126 · livello facile · dispensa
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$?
  1. $0$
  2. $3$
  3. $5$
  4. $-\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.
dp-f-127 · livello facile · dispensa
Come si scrive uno zaino 0-1 (KP) con $n$ oggetti come zaino a scelta multipla (MCKP), dove si sceglie esattamente un oggetto per classe?
  1. Una classe per oggetto, con l'oggetto e un oggetto fittizio di profitto e peso nulli
  2. Una sola classe con tutti gli $n$ oggetti
  3. Due classi, gli oggetti pari e quelli dispari
  4. Non si può: nell'MCKP ogni classe dà esattamente un oggetto
Spiegazione. Scegliere l'oggetto fittizio significa escludere l'oggetto vero: le $2$ scelte per classe sono le $2$ decisioni del KP.
dp-f-128 · livello facile · dispensa
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$?
  1. $-\infty$ per ogni $k\ge 1$
  2. $-\infty$ per $k=0$ e $0$ altrimenti
  3. $k$ per ogni $k$
  4. $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.
dp-f-129 · livello facile · dispensa
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?
  1. Cambia, a meno di ordinare le classi per profitto
  2. Non cambia, ma la PD diventa scorretta
  3. Non cambia: cambiano solo i valori intermedi della tabella
  4. 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.
dp-f-170 · livello facile · dispensa
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?
  1. $2^{12}$ volte una costante
  2. $12\cdot50=600$ volte una costante
  3. $4\cdot2\cdot6\cdot50=2400$ volte una costante
  4. $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.
dp-f-221 · livello facile · dispensa
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?
  1. $\Theta(qc)$
  2. $\Theta(2^q)$
  3. $\Theta(q)$: un passo per classe
  4. $\Theta(n)$: un passo per oggetto
Spiegazione. Risalendo dalla capacità $c$ si legge, classe per classe, l'oggetto scelto: un passo per classe.
dp-f-276 · livello ipotesi · dispensa
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?
  1. Da ogni classe si sceglie al più un oggetto
  2. Gli oggetti sono in copie illimitate
  3. La capacità va riempita esattamente
  4. 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$.
dp-f-277 · livello teorema · dispensa
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?
  1. $\Theta(nc)$; se $v(q,c)=0$
  2. $\Theta(n^2c)$; se $v(q,0)=-\infty$
  3. $\Theta(nc)$; se $v(q,c)=-\infty$
  4. $\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)

dp-f-019 · livello facile · dispensa
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)$?
  1. $50$
  2. $150$
  3. $120$
  4. $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\}$.
dp-f-020 · livello facile · dispensa
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}$?
  1. Quando $w_{dj}\le k_d$ per ogni dimensione $d$
  2. Quando $w_{dj}\le k_d$ per almeno una dimensione $d$
  3. Quando $\sum_d w_{dj}\le\sum_d k_d$
  4. 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.
dp-f-021 · livello facile · dispensa
Nello zaino multidimensionale (MDKP) con $m$ dimensioni e capacità $c_1,\dots,c_m$, perché la PD diventa impraticabile quando $m$ cresce?
  1. Il numero di stati contiene la somma $\sum_d(c_d+1)$, esponenziale in $m$
  2. La ricorrenza perde la sottostruttura ottima appena $m\ge 2$
  3. I sottoproblemi smettono di sovrapporsi appena $m\ge 2$
  4. Il numero di stati contiene il prodotto $\prod_d(c_d+1)$, esponenziale in $m$
Spiegazione. È la maledizione della dimensionalità: ogni dimensione moltiplica il numero di stati per $c_d+1$.
dp-f-130 · livello facile · dispensa
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))$?
  1. $5$
  2. $7$
  3. $9$
  4. $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\}$.
dp-f-131 · livello facile · dispensa
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?
  1. $v(j,\vet k)=p_j+v(j-1,\vet k-\vet w_j)$ se $\sum_d w_{dj}\le\sum_d k_d$
  2. $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
  3. $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$
  4. $v(j,\vet k)=\max_d\{v(j-1,k_d),\ p_j+v(j-1,k_d-w_{dj})\}$
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.
dp-f-132 · livello facile · dispensa
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?
  1. $101^{10}$
  2. $10\cdot 101$
  3. $100^{10}$
  4. $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$.
dp-f-133 · livello facile · dispensa
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$?
  1. $-\infty$ per $\vet k\ne\vet 0$
  2. $\sum_d k_d$
  3. $+\infty$ per ogni $\vet k$
  4. $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.
dp-f-134 · livello facile · dispensa
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?
  1. $j$ resta uguale e $\vet k\leftarrow\vet k-\vet w_j$
  2. $j\leftarrow j-1$ e $\vet k$ resta uguale
  3. $j\leftarrow j-1$ e $\vet k\leftarrow\vet k-\vet w_j$, cioè ogni componente diminuisce del peso dell'oggetto in quella dimensione
  4. $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.
dp-f-135 · livello facile · dispensa
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?
  1. Allo zaino multiplo, con un vettore di capacità
  2. Allo zaino 0-1, con la PD $v(j,k)$ su una sola capacità
  3. Allo zaino illimitato, con la PD $v(k)$
  4. 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$.
dp-f-136 · livello facile · dispensa
Nella PD per lo zaino multidimensionale (MDKP) con $n$ oggetti e capacità $c_1,\dots,c_m$, quanti passi si eseguono?
  1. $\Theta\big(n\prod_d(c_d+1)\big)$: pseudo-polinomiale solo per $m$ fissato
  2. $\Theta\big(n\sum_d c_d\big)$: pseudo-polinomiale per ogni $m$
  3. $\Theta(nm)$: polinomiale
  4. $\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.
dp-f-137 · livello facile · dispensa
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)$?
  1. $75$
  2. $48$
  3. $64$
  4. $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.
dp-f-138 · livello facile · dispensa
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$?
  1. $\Theta(n^2c_1c_2)$, perché le dimensioni sono due
  2. $\Theta(nc_1)$, perché basta la dimensione più vincolante
  3. $\Theta(n\,c_1c_2)$, contro $\Theta(nc)$: una seconda dimensione moltiplica il lavoro per la sua capacità
  4. $\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.
dp-f-171 · livello facile · dispensa
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?
  1. $32$
  2. $231$
  3. $30$
  4. $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.
dp-f-172 · livello ipotesi · dispensa
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?
  1. Se il numero $m$ di dimensioni è fissato: allora è $\Theta(n\prod_dc_d)$, polinomiale nei valori delle capacità
  2. Sempre, per ogni $m$
  3. Solo se tutte le capacità sono uguali
  4. 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à.
dp-f-222 · livello facile · dispensa
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?
  1. $11$
  2. $100$
  3. $1024$
  4. $20$
Spiegazione. $2^{10}=1024$: anche con capacità minime il numero di stati cresce esponenzialmente con le dimensioni. È la maledizione della dimensionalità.
dp-f-278 · livello teorema · dispensa
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$?
  1. Il tempo diventa polinomiale
  2. Il numero di stati non cambia
  3. Gli stati crescono in modo esponenziale in $m$
  4. Il tempo cresce in modo lineare in $m$
Spiegazione. Il prodotto delle $m$ capacità esplode: è la maledizione della dimensionalità.
dp-f-279 · livello ipotesi · dispensa
Sotto quale ipotesi la PD per lo zaino multidimensionale, in $\Theta(m\,n\prod_d(c_d+1))$ passi, è pseudo-polinomiale?
  1. $n\le m$
  2. Il numero $m$ di dimensioni è fissato
  3. Le capacità $c_d$ sono tutte uguali
  4. I profitti sono interi
Spiegazione. Con $m$ costante il tempo è $\Theta(n\prod_d c_d)$, polinomiale nei valori delle capacità; con $m$ nell'input è esponenziale.

8. PD per il problema dello zaino con setup (17)

dp-f-022 · livello facile · dispensa
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?
  1. Una sola volta, nella riga $u(h,0,k)=v(h-1,k-s_h)-f_h$
  2. Una volta per ogni oggetto scelto della classe, sottraendo $f_h$ e $s_h$
  3. Una sola volta, nella riga $v(h,k)$, se $v(h,k)>v(h-1,k)$
  4. 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.
dp-f-023 · livello facile · dispensa
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$?
  1. $v(h,k)=v(h-1,k)+u(h,t_h,k)$
  2. $v(h,k)=\max\{v(h-1,k),\ u(h,0,k)\}$
  3. $v(h,k)=u(h,t_h,k)$
  4. $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)$).
dp-f-024 · livello facile · dispensa
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?
  1. Perché $v(h-1,k)$ non è ancora calcolato a quel punto
  2. Perché $v(h-1,k)$ vale $-\infty$ quando $s_h>0$
  3. Perché si sceglierebbero oggetti della classe senza pagarne il setup
  4. 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.
dp-f-139 · livello facile · dispensa
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?
  1. $5$
  2. $6$
  3. $0$
  4. $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.
dp-f-140 · livello facile · dispensa
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$?
  1. $-f_h$: si paga il setup senza capacità
  2. $v(h-1,k)$: si ignora il setup
  3. $-\infty$: la classe non si può aprire perché il peso di setup non entra
  4. $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.
dp-f-141 · livello facile · dispensa
Nella PD dello zaino con setup (KPS), $v(h,k)$ è il valore ottimo con le classi $1,\dots,h$ e capacità $k$. Quanto vale il caso base $v(0,k)$?
  1. $k$ per ogni $k$
  2. $0$ per ogni $k$
  3. $-\infty$ per $k\ge 1$
  4. $-\sum_h f_h$
Spiegazione. Senza classi la soluzione vuota è ammissibile e non paga setup: vale $0$ per ogni capacità.
dp-f-142 · livello facile · dispensa
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?
  1. 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
  2. Perché $u(h,0,k)$ vale sempre $-\infty$
  3. Perché la classe $h$ ha almeno un oggetto di profitto positivo
  4. 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.
dp-f-143 · livello facile · dispensa
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?
  1. $\Theta(nqc)$
  2. $\Theta(2^qnc)$
  3. $\Theta(nc^2)$
  4. $\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.
dp-f-144 · livello facile · dispensa
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$?
  1. Quante classi aprire in tutto
  2. Se il peso di setup $s_h$ supera la capacità totale $c$
  3. Se la classe $h$ è aperta, confrontando $v(h,k)$ con $v(h-1,k)$
  4. 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.
dp-f-145 · livello facile · dispensa
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à?
  1. Quando la classe ha un solo oggetto
  2. Quando $f_h\ge P_h$: anche prendendo tutti gli oggetti il guadagno netto non è positivo
  3. Quando $f_h\le P_h$
  4. 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.
dp-f-146 · livello facile · dispensa
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$)?
  1. Allo zaino 0-1 sugli stessi oggetti
  2. Allo zaino a scelta multipla, un oggetto per classe
  3. Allo zaino illimitato
  4. 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à.
dp-f-147 · livello facile · dispensa
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?
  1. $u(h,i,k)=\max\{v(h-1,k),\ p_j+v(h-1,k-w_j)\}$
  2. $u(h,i,k)=p_j-f_h+u(h,i-1,k-w_j-s_h)$
  3. $u(h,i,k)=\max\{u(h,i-1,k),\ p_j+u(h,i,k-w_j)\}$
  4. $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ù.
dp-f-173 · livello facile · dispensa
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?
  1. Nulla: i setup si ignorano
  2. Un numero di righe proporzionale a $q$ (apertura e chiusura di ogni classe), assorbito da $\Theta(nc)$ perché $q\le n$
  3. Un fattore $2^q$ per le classi attivate
  4. 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)$.
dp-f-223 · livello facile · dispensa
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$?
  1. $96$
  2. $192$
  3. $120$
  4. $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)$.
dp-f-224 · livello facile · dispensa
Dopo aver calcolato la tabella della PD per lo zaino con setup, quanti passi richiede la ricostruzione degli oggetti e delle classi scelte?
  1. $\Theta(q)$
  2. $\Theta(c)$
  3. $\Theta(n)$
  4. $\Theta(nc)$
Spiegazione. Si risale la tabella riga per riga, con un passo per oggetto e per riga di setup: $\Theta(n+q)=\Theta(n)$.
dp-f-280 · livello ipotesi · dispensa
Nella PD per lo zaino con setup la classe $h$ si apre con $u(h,0,k)=v(h-1,k-s_h)-f_h$. Che cosa garantisce questo valore iniziale?
  1. La classe $h$ resta sempre chiusa
  2. Il setup non occupa capacità
  3. Il setup (peso $s_h$, costo $f_h$) si paga una sola volta per classe
  4. Il setup si paga per ogni oggetto della classe
Spiegazione. Il costo e il peso di setup si tolgono all'apertura della classe; poi si prosegue con la ricorrenza del KP sui suoi oggetti.
dp-f-281 · livello teorema · dispensa
Quanti passi esegue la PD per lo zaino con setup con $n$ oggetti e capacità $c$?
  1. $\Theta(nc^2)$
  2. $\Theta(nc)$
  3. $\Theta(n^2c)$
  4. $\Theta(2^q nc)$
Spiegazione. Come la PD dello zaino 0/1: un numero costante di confronti per ogni oggetto e ogni capacità, più i confronti delle classi.

9. PD per il problema degli zaini multipli (19)

dp-f-025 · livello facile · dispensa
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?
  1. Diminuiscono tutte le componenti, di $w_j$
  2. Diminuiscono tutte le componenti, di $w_j/m$
  3. Non cambia: le capacità si controllano alla fine
  4. 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.
dp-f-026 · livello facile · dispensa
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})$?
  1. $2$: l'oggetto $j$ è scelto o no, indipendentemente dallo zaino
  2. $m$: l'oggetto $j$ va sempre in uno degli zaini in cui entra
  3. $m+1$: l'oggetto $j$ resta fuori o va in uno degli zaini in cui entra
  4. $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$.
dp-f-027 · livello facile · dispensa
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$?
  1. Il valore di una soluzione ammissibile dell'MKP
  2. Un upper bound: la soluzione può non essere divisibile fra gli zaini
  3. Un lower bound: la soluzione si divide sempre fra gli zaini
  4. 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.
dp-f-148 · livello facile · dispensa
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?
  1. $9$
  2. $8$
  3. $13$
  4. $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.
dp-f-149 · livello facile · dispensa
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?
  1. $v(j,\vet k)=\max\{v(j-1,\vet k),\ p_j+v(j-1,\vet k-w_j\vet 1)\}$
  2. $v(j,\vet k)=\max_i\{p_j+v(j-1,\vet k-w_j\vet e_i)\}$
  3. $v(j,\vet k)=\max\{v(j-1,\vet k),\ p_j+v(j,\vet k-w_j\vet e_1)\}$
  4. $v(j,\vet k)=\max\{v(j-1,\vet k),\ \max_{i:\,w_j\le k_i}\{p_j+v(j-1,\vet k-w_j\vet e_i)\}\}$
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.
dp-f-150 · livello facile · dispensa
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?
  1. Eliminando gli zaini vuoti dallo stato
  2. Non si può: la PD deve distinguere gli zaini
  3. Tenendo solo i vettori ordinati, per esempio con componenti non crescenti
  4. 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$.
dp-f-151 · livello facile · dispensa
Nella PD per lo zaino multiplo (MKP) con $m$ zaini di capacità $c$ e $n$ oggetti, come cresce il numero di stati con il numero di zaini?
  1. Come $2^n$, indipendentemente da $m$
  2. Come $(c+1)^m$ per oggetto: esponenzialmente in $m$
  3. Come $m(c+1)$: linearmente in $m$
  4. Come $c^2$, indipendentemente da $m$
Spiegazione. Lo stato contiene una capacità residua per zaino: $\prod_i(c_i+1)=(c+1)^m$ vettori. Per questo la PD è praticabile solo con pochi zaini.
dp-f-152 · livello facile · dispensa
Nella PD per lo zaino multiplo (MKP), quanto vale il caso base $v(0,\vet k)$, senza oggetti e con capacità residue $\vet k$?
  1. $0$ per ogni $\vet k$
  2. $-\infty$ se qualche $k_i>0$
  3. $\sum_i k_i$
  4. $+\infty$ per ogni $\vet k$
Spiegazione. Senza oggetti tutti gli zaini restano vuoti, soluzione ammissibile di valore $0$ per ogni vettore di capacità.
dp-f-153 · livello facile · dispensa
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?
  1. Solo se l'oggetto $j$ è scelto o no
  2. Il profitto totale dello zaino più pieno
  3. Il vettore $\vet k$ dello stato successivo
  4. 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.
dp-f-154 · livello facile · dispensa
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$?
  1. Allo zaino multidimensionale con una dimensione per oggetto
  2. Al bin packing con un contenitore
  3. Allo zaino 0-1 con capacità $c_1$
  4. 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$.
dp-f-155 · livello facile · dispensa
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)$?
  1. $40$
  2. $120$
  3. $96$
  4. $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.
dp-f-156 · livello facile · dispensa
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$?
  1. $\Theta\big(nm\prod_i(c_i+1)\big)$
  2. $\Theta\big(n\sum_i c_i\big)$
  3. $\Theta\big(n(m+1)\big)$
  4. $\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.
dp-f-174 · livello facile · dispensa
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?
  1. $35$
  2. $12$
  3. $48$
  4. $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.
dp-f-225 · livello facile · dispensa
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?
  1. $72$
  2. $96$
  3. $60$
  4. $112$
Spiegazione. $N=2\cdot3=6$: $3\cdot2\cdot2\cdot6=72$, $2\cdot2\cdot6=24$, $2\cdot6=12$, poi $2+2$: $112$.
dp-f-226 · livello facile · dispensa
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?
  1. $7$
  2. $8$
  3. $27$
  4. $9$
Spiegazione. $(2+1)^3=27$: un valore di capacità residua per zaino, combinati in tutti i modi.
dp-f-227 · livello facile · dispensa
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$)?
  1. $13$ e $39$
  2. $13$ e $125$
  3. $13$ e $15$
  4. $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.
dp-f-228 · livello teorema · dispensa
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?
  1. Per $m$ fissato il prodotto è un polinomio di grado $m$ nelle capacità; con $m$ variabile l'esponente cresce con l'istanza
  2. Perché per $m$ fissato il problema è in P
  3. Perché il numero di oggetti non conta
  4. È 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.
dp-f-282 · livello teorema · dispensa
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?
  1. $m$; $\Theta(n\,m^2)$
  2. $2^m$; $\Theta(n\sum_i c_i)$
  3. $m+1$; $\Theta(m\,n\prod_i(c_i+1))$
  4. $2$; $\Theta(nc)$
Spiegazione. L'oggetto resta fuori o va in uno degli $m$ zaini; gli stati sono $n\prod_i(c_i+1)$.
dp-f-283 · livello ipotesi · dispensa
Per gli zaini multipli, perché non basta riempire uno zaino alla volta con la PD dello zaino 0/1 sugli oggetti rimasti?
  1. Perché gli oggetti sono in copie illimitate
  2. Le scelte di uno zaino dipendono dagli altri: così si può perdere l'ottimo
  3. Perché la PD dello zaino 0/1 non è esatta
  4. Perché le capacità devono essere uguali
Spiegazione. Un riempimento ottimo del primo zaino può togliere oggetti che servirebbero agli altri: la PD deve guardare tutte le capacità insieme.

10. PD per il problema del lot sizing senza capacità (31)

dp-f-028 · livello teorema · dispensa
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?
  1. Ogni istanza dell'ULS ha una soluzione ottima con $s_t\,x_t=0$ per ogni periodo $t$
  2. Ogni istanza dell'ULS ha una soluzione ottima con $s_{t-1}\,x_t=0$ per ogni periodo $t$
  3. Ogni soluzione ottima dell'ULS ha $s_{t-1}\,x_t=0$ per ogni periodo $t$
  4. 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.
dp-f-029 · livello ipotesi · dispensa
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?
  1. Costi non negativi e produzione senza limiti, per spostare produzione fra due periodi senza aumentare il costo
  2. Costi non negativi e capacità costanti, per spostare produzione fra due periodi senza aumentare il costo
  3. Costi di mantenimento nulli e produzione senza limiti, così le scorte non costano mai nulla
  4. 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.
dp-f-030 · livello facile · dispensa
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?
  1. $\Theta(m^3)$
  2. $\Theta(2^m)$
  3. $\Theta(m\,D_{1,m})$
  4. $\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)$.
dp-f-103 · livello facile · dispensa
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}$?
  1. $130$
  2. $160$
  3. $180$
  4. $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.
dp-f-104 · livello facile · dispensa
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?
  1. $c_{j,t}=c_{j,t-1}\cdot d_t$
  2. $c_{j,t}=c_{j,t-1}+\big(vc_j+\sum_{k=j}^{t-1}hc_k\big)\,d_t$
  3. $c_{j,t}=c_{j,t-1}+sc_j+vc_j\,d_t$
  4. $c_{j,t}=c_{j,t-1}+hc_t\,d_t$
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)$.
dp-f-105 · livello facile · dispensa
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$?
  1. $15$
  2. $25$
  3. $10$
  4. $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.
dp-f-106 · livello facile · dispensa
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)$?
  1. $220$
  2. $230$
  3. $300$
  4. $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$.
dp-f-107 · livello facile · dispensa
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$?
  1. Si registra un lotto in ogni periodo $t$ con $v(t)<v(t-1)$
  2. Si registrano i lotti in $j^*(1),j^*(2),\dots,j^*(m)$, in avanti
  3. Si registra un lotto in $j^*(t)$ e si pone $t\leftarrow j^*(t)-1$, fino a $t=0$
  4. 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$.
dp-f-108 · livello facile · dispensa
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}\}$?
  1. La quantità prodotta nel periodo $t$
  2. Il periodo dell'ultimo lotto, che produce le domande dei periodi $j,\dots,t$
  3. Il periodo del primo lotto, che produce le domande dei periodi $1,\dots,j$
  4. 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$.
dp-f-109 · livello facile · dispensa
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$?
  1. $32$
  2. $64$
  3. $21$
  4. $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.
dp-f-110 · livello facile · dispensa
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?
  1. Esattamente la domanda $d_j$ del proprio periodo
  2. La domanda totale $D_{1,m}$ di tutti i periodi
  3. Una quantità qualsiasi, purché la scorta resti non negativa
  4. 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.
dp-f-111 · livello facile · dispensa
Nell'algoritmo di Wagner e Whitin per il lot sizing senza capacità, $v(t)$ è il costo ottimo dei periodi $1,\dots,t$. Perché il caso base è $v(0)=0$?
  1. Perché la scorta iniziale è pari alla domanda del periodo $1$
  2. Perché $v(0)$ non viene mai letto dalla ricorrenza
  3. Un insieme vuoto di periodi non ha domanda né costi
  4. Perché il primo periodo non ha costo di setup
Spiegazione. $v(0)$ è letto dal termine $j=1$: $v(t)=v(0)+c_{1,t}$ è il piano con un solo lotto nel periodo $1$, e il suo costo è proprio $c_{1,t}$.
dp-f-175 · livello facile · dispensa
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}$?
  1. $40$
  2. $110$
  3. $80$
  4. $70$
Spiegazione. $D_{2,4}=d_2+d_3+d_4=10+30+40=80$. $70$ dimentica $d_2$; $110$ è la domanda totale.
dp-f-176 · livello facile · dispensa
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?
  1. $(30,0,70,0,20)$
  2. $(30,0,70,0,10)$
  3. $(10,20,30,40,10)$
  4. $(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$.
dp-f-177 · livello facile · dispensa
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}$?
  1. $120$
  2. $110$
  3. $90$
  4. $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.
dp-f-178 · livello teorema · dispensa
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}$?
  1. Perché ogni unità resta a scorta un solo periodo
  2. Perché si tiene a scorta la domanda dei periodi da $j$ a $k$
  3. Perché il costo di mantenimento si paga solo nel periodo del setup
  4. 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à.
dp-f-179 · livello facile · dispensa
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?
  1. $\Theta(m)$: un termine per periodo
  2. $\Theta(m\,D_{1,m})$: pseudo-polinomiale nella domanda
  3. $\Theta(m^2)$: una coppia $(j,t)$ con $j\le t$ per ogni termine del minimo
  4. $\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.
dp-f-229 · livello facile · dispensa
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?
  1. $x_t\le D_{t,m}\,y_t$, con $D_{t,m}$ la domanda dei periodi da $t$ a $m$
  2. $s_{t-1}+x_t=d_t+s_t$
  3. $y_t\le x_t$
  4. $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à.
dp-f-230 · livello facile · dispensa
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?
  1. $110$
  2. $50$
  3. $360$
  4. $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.
dp-f-231 · livello facile · dispensa
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}$?
  1. Sì: $(40,30,0,50,0)$
  2. No: $s_3<0$
  3. Sì: $(40,30,0,10,0)$
  4. 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.
dp-f-232 · livello facile · dispensa
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?
  1. $120$
  2. $16$
  3. $32$
  4. $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.
dp-f-233 · livello facile · dispensa
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}$?
  1. $90$
  2. $70$
  3. $120$
  4. $50$
Spiegazione. $50+hc_3D_{4,4}=50+40=90$: la domanda del periodo $4$ resta a scorta un periodo.
dp-f-234 · livello facile · dispensa
Nell'algoritmo di Wagner e Whitin, oltre al calcolo della matrice dei costi, il numero di passi è $3+3m+3\sum_{t=1}^mt$. Quanto vale per $m=4$?
  1. $30$
  2. $27$
  3. $63$
  4. $45$
Spiegazione. $3+12+3\cdot10=45$. Il termine $\sum_tt=m(m+1)/2$ dà l'ordine $\Theta(m^2)$.
dp-f-235 · livello facile · dispensa
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?
  1. $10$
  2. $32$
  3. $15$
  4. $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.
dp-f-284 · livello teorema · dispensa
Che cosa afferma la proprietà zero-inventory ordering (Wagner e Whitin) per il lot sizing senza capacità (ULS), con produzioni $x_t$ e scorte $s_t$?
  1. Ogni soluzione ammissibile ha $x_t=d_t$
  2. Esiste una soluzione ottima con $s_{t-1}\,x_t=0$ per ogni $t$
  3. Ogni soluzione ottima produce in ogni periodo
  4. Esiste una soluzione ottima con $s_t>0$ per ogni $t$
Spiegazione. Un periodo produce solo se arriva con la scorta vuota: la produzione di un periodo copre la domanda di periodi consecutivi.
dp-f-285 · livello ipotesi · dispensa
Sotto quali ipotesi vale la proprietà zero-inventory ordering del lot sizing?
  1. Nessuna capacità di produzione e costi non negativi
  2. Capacità costanti e costi qualunque
  3. Domande tutte uguali
  4. Costi di setup nulli
Spiegazione. Con produzione illimitata e costi non negativi conviene produrre solo a scorta vuota; con le capacità la proprietà cade.
dp-f-286 · livello teorema · dispensa
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?
  1. $\Theta(m)$; un albero ricoprente minimo
  2. $\Theta(2^m)$; tutti i piani di produzione
  3. $\Theta(m^3)$; un flusso massimo
  4. $\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$.
dp-f-287 · livello ipotesi · dispensa
Nel lot sizing senza capacità, perché un lotto di produzione che copre i periodi $j,\dots,t$ produce esattamente $D_{j,t}=d_j+\dots+d_t$?
  1. Perché la capacità vale $D_{j,t}$
  2. Perché i costi di setup sono nulli
  3. Per la proprietà zero-inventory ordering
  4. Perché le domande sono uguali
Spiegazione. Il periodo $j$ produce a scorta vuota e il prossimo lotto parte a scorta vuota: si produce tutta e sola la domanda dei periodi coperti.
dp-f-306 · livello facile · dispensa
Nel lot sizing senza capacità (ULS) con $m$ periodi, domande $d_t$, costi di setup, di produzione e di giacenza: che cosa si decide?
  1. Quali oggetti mettere nello zaino
  2. In che ordine visitare i periodi
  3. Quante macchine usare
  4. Quanto produrre in ogni periodo, soddisfacendo le domande a costo minimo
Spiegazione. La soluzione è il vettore delle produzioni $(x_1,\dots,x_m)$; le scorte seguono dalle produzioni e dalle domande.
dp-f-307 · livello facile · dispensa
Nella PD di Wagner e Whitin, che cosa rappresenta $c_{j,t}$?
  1. La capacità del periodo $j$
  2. Il valore ottimo dei primi $t$ periodi
  3. Il costo di produrre nel periodo $j$ la domanda dei periodi $j,\dots,t$
  4. La domanda totale dei periodi $j,\dots,t$
Spiegazione. È il costo di un lotto: setup in $j$, produzione di $D_{j,t}$ e giacenza delle unità fino al loro periodo.
dp-f-308 · livello facile · dispensa
Nella PD di Wagner e Whitin si memorizza $r[t]$, il periodo dell'ultimo lotto che copre il periodo $t$. A che cosa serve?
  1. A ordinare i periodi
  2. A ricostruire a ritroso un piano di produzione ottimo
  3. A calcolare le domande totali
  4. A verificare le capacità
Spiegazione. Da $t=m$ si legge il periodo $r[m]$ dell'ultimo lotto, poi si riparte da $r[m]-1$, fino al periodo $0$.

11. PD per il problema del lot sizing capacitato (28)

dp-f-031 · livello facile · dispensa
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?
  1. Il periodo $t$ dell'ultimo lotto prodotto, come nell'ULS; il valore ottimo è $v(m)$
  2. La coppia $(t,x)$ del periodo e della produzione, con $x\le cap_t$; il valore ottimo è $v(m,cap_m)$
  3. La coppia $(t,k)$ del periodo e della scorta finale, con $k\le D_{t+1,m}$; il valore ottimo è $v(m,0)$
  4. 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.
dp-f-032 · livello facile · dispensa
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$?
  1. $k$: una unità di costo per ogni unità di scorta
  2. $+\infty$: questi stati non sono raggiungibili
  3. $0$: nessun costo è ancora stato pagato
  4. $-\infty$: questi stati non sono raggiungibili
Spiegazione. Il valore $+\infty$ segna gli stati che non si possono raggiungere; solo $v(0,0)=0$.
dp-f-033 · livello teorema · dispensa
Nel lot sizing con capacità (CLS) su $m$ periodi, con domanda totale $D$ e capacità massima $C$, quale affermazione sulla complessità è corretta?
  1. La PD esegue $O(mDC)$ passi; con capacità costante è polinomiale, con capacità generali NP-difficile
  2. La PD esegue $O(mDC)$ passi; con capacità costante è NP-difficile in senso forte
  3. La PD di Wagner e Whitin sui lotti risolve anche il CLS in $\Theta(m^2)$ passi
  4. 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.
dp-f-112 · livello facile · dispensa
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é?
  1. Perché gli stati con scorta maggiore hanno costo nullo
  2. Una scorta maggiore della domanda residua resterebbe inutilizzata e violerebbe la scorta finale nulla
  3. Perché la capacità del periodo $t$ è al più $D_{t+1,m}$
  4. 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.
dp-f-113 · livello facile · dispensa
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?
  1. $20$
  2. $22$
  3. $12$
  4. $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.
dp-f-114 · livello facile · dispensa
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)$?
  1. Da tutti gli stati $(t-1,k')$ con $k'\le k$
  2. Solo dallo stato $(t-1,0)$, per la proprietà zero-inventory
  3. Da quelli con $k'=k+d_t$
  4. 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ù.
dp-f-115 · livello facile · dispensa
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)$?
  1. Ci sono $2^m$ scelte di setup, ciascuna valutata in $O(DC)$
  2. Ci sono $D\cdot C$ stati e $m$ transizioni per stato
  3. Ci sono al più $m(D+1)$ stati $(t,k)$, e ognuno ha al più $C+1$ transizioni, una per produzione
  4. 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$.
dp-f-116 · livello teorema · dispensa
Perché l'algoritmo di Wagner e Whitin, che sceglie solo i periodi dei lotti, non risolve il lot sizing con capacità (CLS)?
  1. Perché il CLS ha scorta finale libera
  2. Con le capacità può non esistere un piano ottimo con produzione solo a scorta in ingresso nulla
  3. Perché nel CLS i costi di setup sono nulli
  4. 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.
dp-f-117 · livello facile · dispensa
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?
  1. $sc_t$ se $x>0$, più $vc_t\,x$, più $hc_t\,k$ per la scorta finale del periodo $t$
  2. Sempre $sc_t$, più $vc_t\,x$
  3. $sc_t$ se $x>0$, più $hc_t\,k'$ per la scorta iniziale
  4. 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.
dp-f-118 · livello facile · dispensa
Nella PD del lot sizing con capacità, la capacità del periodo $t$ è $cap_t=3$. Da quanti stati $(t-1,k')$ si può arrivare al più a uno stato $(t,k)$?
  1. $3$, uno per ogni unità di capacità
  2. $2$: produrre o no
  3. $k+1$, uno per ogni scorta minore
  4. $4$, uno per ogni produzione $x\in\{0,1,2,3\}$
Spiegazione. Fissati $k$ e $d_t$, la scorta precedente è $k'=k+d_t-x$: una per ogni produzione ammessa, purché $k'\ge 0$ e nel campo degli stati.
dp-f-119 · livello facile · dispensa
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$?
  1. $v(1,k)=0$ per ogni $k$, perché il periodo $1$ non produce
  2. $v(1,1)=sc_1+hc_1$, con una unità in scorta
  3. $v(1,k)=+\infty$ per ogni $k$: la domanda del periodo $1$ supera la sua capacità
  4. $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.
dp-f-120 · livello facile · dispensa
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?
  1. Basta l'algoritmo di Wagner e Whitin senza modifiche
  2. Il problema si risolve in tempo polinomiale
  3. Il problema resta NP-difficile in senso forte
  4. 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.
dp-f-180 · livello facile · dispensa
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. $(1,0,0,1,0)$
  2. $(1,0,1,1,0)$
  3. $(1,1,1,1,0)$
  4. $(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.
dp-f-181 · livello facile · dispensa
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}$?
  1. La scorta deve essere vuota alla fine dell'orizzonte, quindi non supera mai la domanda dei periodi successivi
  2. Perché la capacità è al più $D_{t+1,m}$
  3. Perché la scorta è sempre nulla
  4. 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.
dp-f-182 · livello facile · dispensa
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$?
  1. Perché si produce sempre $d_t$
  2. Perché la scorta del periodo precedente è sempre $k$
  3. Perché la domanda si paga nel periodo successivo
  4. 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\}\}$.
dp-f-183 · livello teorema · dispensa
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?
  1. Esponenziale in $m$
  2. Lineare nella dimensione dell'istanza
  3. Pseudo-polinomiale: è polinomiale nei valori numerici $D$ e $C$, non nella loro lunghezza in bit
  4. 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.
dp-f-184 · livello ipotesi · dispensa
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?
  1. Ogni periodo produce esattamente la propria domanda
  2. 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$
  3. Si produce solo con scorta vuota
  4. 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.
dp-f-236 · livello facile · dispensa
Lot sizing capacitato con domande $d=(2,1,3,4,1)$ e capacità $cap_t=4$ in ogni periodo. Quale piano è inammissibile?
  1. $(4,0,2,4,1)$
  2. $(6,0,0,5,0)$
  3. $(3,0,4,4,0)$
  4. $(2,1,3,4,1)$
Spiegazione. $(6,0,0,5,0)$ supera la capacità nei periodi $1$ e $4$. Gli altri hanno scorte non negative, finale nulla e produzioni al più $4$.
dp-f-237 · livello ipotesi · dispensa
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?
  1. Si basa sulla proprietà zero-inventory, che con le capacità non vale: un lotto può non entrare nella capacità del suo periodo
  2. Perché con le capacità i costi di setup sono nulli
  3. Perché il CLS ha un solo periodo
  4. 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).
dp-f-238 · livello facile · dispensa
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?
  1. $55$
  2. $25$
  3. $11$
  4. $28$
Spiegazione. $D_{2,5}=9$, $D_{3,5}=8$, $D_{4,5}=5$, $D_{5,5}=1$, $D_{6,5}=0$: $10+9+6+2+1=28$ stati.
dp-f-239 · livello facile · dispensa
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?
  1. Da $m^2$ coppie di periodi
  2. Da $D\cdot C$ coppie di periodi
  3. Al più $D+1$ scorte per ciascuno degli $m$ periodi, e al più $C+1$ produzioni per stato
  4. Da $2^m$ piani di setup
Spiegazione. Stati $O(mD)$ per tentativi $O(C)$: pseudo-polinomiale nei valori $D$ e $C$.
dp-f-240 · livello facile · dispensa
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?
  1. Ogni periodo produce la propria domanda
  2. 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$
  3. Ogni periodo produce esattamente $4$
  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.
dp-f-288 · livello teorema · dispensa
Nella PD per il lot sizing capacitato (CLS) lo stato è $(t,k)$, con $k$ la scorta a fine periodo $t$. Dove si legge il valore ottimo, con $m$ periodi?
  1. In $v(1,0)$
  2. In $v(m,0)$
  3. In $v(0,m)$
  4. In $\max_k v(m,k)$
Spiegazione. Alla fine dell'orizzonte la scorta è zero: il valore ottimo è quello dello stato $(m,0)$.
dp-f-289 · livello ipotesi · dispensa
Perché la PD di Wagner e Whitin sui lotti di produzione non si applica al lot sizing capacitato?
  1. Con le capacità la proprietà zero-inventory ordering non vale
  2. Perché i costi possono essere negativi
  3. Perché la rete dei lotti ha cicli
  4. Perché le domande non sono intere
Spiegazione. Con capacità limitate un periodo può dover produrre con unità ancora in scorta: un lotto non produce più esattamente $D_{j,t}$.
dp-f-290 · livello teorema · dispensa
Che cosa si sa della complessità del lot sizing capacitato a un prodotto?
  1. È sempre polinomiale
  2. È NP-difficile anche senza capacità
  3. Con capacità costante è NP-difficile
  4. 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.
dp-f-291 · livello ipotesi · dispensa
La PD per il lot sizing capacitato esegue $O(mDC)$ passi, con $D$ la domanda totale e $C$ la capacità massima. Perché è pseudo-polinomiale?
  1. Perché la scorta è sempre zero
  2. Perché la rete ha $2^m$ archi
  3. Il tempo dipende dai valori $D$ e $C$, non solo da $m$
  4. Perché $m$ è esponenziale
Spiegazione. Gli stati sono indicizzati dalle quantità in scorta: il numero di passi cresce con i valori numerici dei dati.
dp-f-309 · livello facile · dispensa
Che cosa aggiunge il lot sizing capacitato (CLS) al lot sizing senza capacità?
  1. Un limite $cap_t$ alla produzione di ogni periodo
  2. Un limite alle scorte finali
  3. Più prodotti
  4. Domande incerte
Spiegazione. Il vincolo $x_t\le cap_t$ limita la produzione di ogni periodo.
dp-f-310 · livello facile · dispensa
Nella PD per il lot sizing capacitato, che cosa sceglie la ricorrenza $v(t,k)$ nel periodo $t$?
  1. Il periodo dell'ultimo lotto
  2. Quale prodotto fare
  3. La capacità del periodo
  4. La quantità $x$ prodotta nel periodo $t$
Spiegazione. Dallo stato $(t,k)$ con scorta finale $k$ si prova ogni produzione $x\le cap_t$ compatibile con la domanda $d_t$.

12. PD per il problema del cambio monete (23)

dp-f-034 · livello facile · dispensa
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$?
  1. $+\infty$
  2. $0$
  3. $2$
  4. $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.
dp-f-035 · livello facile · dispensa
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'è?
  1. Il CCP chiede somma al più $c$ e minimizza le monete; l'UKP chiede peso esattamente $c$ e massimizza il profitto
  2. Il CCP chiede somma esattamente $c$ e massimizza le monete; l'UKP chiede peso al più $c$ e minimizza il peso
  3. Il CCP ammette al più una moneta per taglio; l'UKP ammette copie illimitate di ogni tipo
  4. 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.
dp-f-036 · livello facile · dispensa
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?
  1. $\Theta(n^c)$
  2. $\Theta(c\log n)$, polinomiale
  3. $\Theta(nc)$, pseudo-polinomiale
  4. $\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.
dp-f-085 · livello facile · dispensa
Nel cambio monete (CCP) i tagli $w_1,\dots,w_n$ sono disponibili in quantità illimitata e il resto è $c$. Che cos'è una soluzione ammissibile?
  1. Un vettore binario $x$ con $\sum_j w_jx_j\ge c$
  2. Un vettore intero $x\ge 0$ con $\sum_j w_jx_j=c$
  3. Un vettore intero $x\ge 0$ con $\sum_j w_jx_j\le c$
  4. Un sottoinsieme dei tagli di somma $c$
Spiegazione. $x_j$ conta le monete del taglio $j$, e la somma deve essere esattamente il resto. L'obiettivo minimizza $\sum_j x_j$.
dp-f-086 · livello facile · dispensa
Cambio monete (CCP) con tagli $w=(4,6)$, in quantità illimitata, e resto $c=9$. Quante monete servono al minimo?
  1. Nessuna soluzione: con tagli pari non si ottiene un resto dispari
  2. $2$
  3. $3$
  4. $1$
Spiegazione. Ogni combinazione di $4$ e $6$ è pari, quindi $9$ non si ottiene e l'istanza non ha soluzioni ammissibili: la PD dà $v(9)=+\infty$.
dp-f-087 · livello facile · dispensa
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?
  1. $12$
  2. $27$
  3. $64$
  4. $42$
Spiegazione. $(6+1)(2+1)(1+1)=7\cdot3\cdot2=42$; solo quelli con somma esattamente $6$ sono ammissibili.
dp-f-088 · livello facile · dispensa
Cambio monete (CCP) con tagli $w=(1,3,4)$ e resto $c=6$. Con $v(0)=0$ e $v(k)=\min_{j:\,w_j\le k}\{1+v(k-w_j)\}$, quanto vale $v(6)$?
  1. $6$
  2. $1$
  3. $2$
  4. $3$
Spiegazione. $6=3+3$ usa $2$ monete. Il greedy che prende sempre il taglio più grande usa $4+1+1$, cioè $3$ monete: con questi tagli non è ottimo.
dp-f-089 · livello facile · dispensa
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?
  1. $k$: si usano monete da $1$
  2. $+\infty$: il resto $k$ non si può dare
  3. $0$: non serve nessuna moneta
  4. $-\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.
dp-f-090 · livello facile · dispensa
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$?
  1. Partendo da $k=c$: si prende una moneta $w_{s(k)}$ e si pone $k\leftarrow k-w_{s(k)}$, fino a $k=0$
  2. Si prendono $v(c)$ monete del taglio $s(c)$
  3. Partendo da $k=0$: si prende $w_{s(k)}$ e si pone $k\leftarrow k+w_{s(k)}$
  4. 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.
dp-f-091 · livello facile · dispensa
Nell'albero di ricorsione della PD per il cambio monete, ogni nodo è una chiamata $v(k)$. Quanti figli ha il nodo $v(k)$?
  1. Due: usare o non usare il taglio $1$
  2. $k$, uno per ogni resto minore
  3. Uno solo, con il taglio più grande che entra
  4. 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.
dp-f-092 · livello facile · dispensa
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)$?
  1. $2$
  2. $3$
  3. $4$
  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.
dp-f-093 · livello facile · dispensa
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?
  1. Nessuna: con $p_j=1$ le due ricorrenze coincidono
  2. Minimo invece di massimo, e $+\infty$ per i resti non ottenibili perché la somma deve essere esatta
  3. Copie limitate invece che illimitate, e tabella bidimensionale
  4. 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$.
dp-f-185 · livello facile · dispensa
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?
  1. $\sum_jw_jx_j\ge c$
  2. $\sum_jw_jx_j=c$ con $x_j\in\Z_{\ge0}$
  3. $\sum_jw_jx_j\le c$ con $x_j\in\{0,1\}$
  4. $\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.
dp-f-186 · livello facile · dispensa
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?
  1. $\Theta(nc)$, pseudo-polinomiale: dipende dal valore $c$, non dalla sua lunghezza in bit
  2. $\Theta(n\log c)$, polinomiale
  3. $\Theta(2^n)$, esponenziale nel numero di tagli
  4. $\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.
dp-f-241 · livello facile · dispensa
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»?
  1. $(6,0,0)$ con $6$ monete; il greedy ne usa $3$
  2. $(0,2,0)$ con $2$ monete; il greedy ne usa $3$ ($4+1+1$)
  3. $(2,0,1)$ con $3$ monete; il greedy ne usa $3$
  4. $(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.
dp-f-242 · livello facile · dispensa
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?
  1. $x_1\le6$, $x_2\le2$, $x_3\le1$
  2. $x_j\le1$ per ogni $j$
  3. $x_1\le6$, $x_2\le3$, $x_3\le2$
  4. $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$.
dp-f-243 · livello facile · dispensa
La PD per il cambio monete esegue $S(n,c)=3+3c+3cn$ passi. Quanti sono con $n=3$ tagli e resto $c=6$?
  1. $54$
  2. $21$
  3. $57$
  4. $75$
Spiegazione. $3+18+54=75$; il termine dominante $3cn$ dà $\Theta(nc)$.
dp-f-292 · livello teorema · dispensa
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?
  1. Il minimo numero di monete; $\Theta(c\log c)$
  2. Il massimo valore con $k$ monete; $\Theta(n^2)$
  3. Il minimo numero di monete per l'importo $k$; $\Theta(nc)$
  4. 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.
dp-f-293 · livello ipotesi · dispensa
Nella PD per il cambio monete gli importi che non si possono formare hanno $v(k)=+\infty$ e non $0$. Perché?
  1. Perché $v(0)=+\infty$
  2. Il resto va dato esattamente e si minimizza il numero di monete
  3. Perché i tagli sono positivi
  4. Perché la capacità può restare inutilizzata
Spiegazione. Con $0$ un importo impossibile sembrerebbe il migliore; $+\infty$ lo esclude dal minimo. L'istanza è inammissibile se $v(c)=+\infty$.
dp-f-294 · livello teorema · dispensa
Tagli $\{1,3,4\}$, importo $6$. Che cosa danno il greedy «moneta più grande che entra» e la PD per il cambio monete?
  1. Greedy $3$ monete ($4+1+1$), PD $2$ monete ($3+3$)
  2. Entrambi $2$ monete
  3. Greedy $2$ monete, PD $3$ monete
  4. Entrambi $3$ monete
Spiegazione. Il greedy non è esatto per tagli qualunque; la PD trova sempre il minimo: $v(6)=2$.
dp-f-311 · livello facile · dispensa
Che cosa chiede il problema del cambio monete (CCP)?
  1. Il massimo numero di monete con valore al più $c$
  2. Il numero di modi di formare $c$
  3. La moneta più grande che entra in $c$
  4. Il minimo numero di monete che formano esattamente l'importo $c$
Spiegazione. Ogni taglio è disponibile in copie illimitate e il totale deve essere esattamente $c$.
dp-f-312 · livello facile · dispensa
Tagli $\{1,2,5\}$, importo $11$. Quanto vale il minimo numero di monete $v(11)$?
  1. $2$
  2. $5$
  3. $3$
  4. $4$
Spiegazione. $11=5+5+1$ con $3$ monete; con $2$ monete il massimo è $10$.
dp-f-313 · livello facile · dispensa
Tagli $\{4,6\}$, importo $9$. Che cosa dà la PD per il cambio monete?
  1. $v(9)=0$
  2. $v(9)=+\infty$: l'istanza è inammissibile
  3. $v(9)=2$
  4. $v(9)=3$
Spiegazione. Con tagli pari si formano solo importi pari: $9$ non si può formare.

13. PD per il problema del taglio delle aste (28)

dp-f-037 · livello facile · dispensa
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$?
  1. $5$
  2. $16$
  3. $32$
  4. $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.
dp-f-038 · livello facile · dispensa
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 è?
  1. L'input contiene gli $n$ prezzi, quindi $n$ cresce con la dimensione dell'istanza
  2. I prezzi $p_j$ sono interi, quindi la tabella ha valori interi
  3. La lunghezza $n$ è scritta in binario con $\log n$ cifre
  4. 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.
dp-f-039 · livello facile · dispensa
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$?
  1. A vietare l'asta senza tagli, che non è uno schema ammissibile
  2. A garantire che l'asta venga tagliata almeno una volta
  3. A nulla: la ricorrenza non legge mai la cella $v(0)$
  4. 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.
dp-f-094 · livello facile · dispensa
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)$?
  1. $16$
  2. $5$
  3. $10$
  4. $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)$.
dp-f-095 · livello facile · dispensa
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)$?
  1. $9$
  2. $11$
  3. $20$
  4. $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$.
dp-f-096 · livello facile · dispensa
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$?
  1. Partendo da $\ell=1$ e aggiungendo pezzi finché la somma è $n$
  2. Si legge $v(n)$ e si divide per il prezzo massimo
  3. Partendo da $\ell=n$: si taglia un pezzo $s(\ell)$ e si pone $\ell\leftarrow\ell-s(\ell)$, fino a $\ell=0$
  4. 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.
dp-f-097 · livello facile · dispensa
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$?
  1. Perché la tabella parte da $\ell=1$
  2. Senza lunghezze di pezzo disponibili un'asta di lunghezza positiva non si può dividere: nessuna soluzione
  3. Perché i prezzi possono essere negativi
  4. 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$.
dp-f-098 · livello facile · dispensa
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)$?
  1. Tagliare un pezzo di lunghezza $j$, potendo tagliarne altri della stessa lunghezza
  2. Non usare pezzi di lunghezza $j$
  3. Tagliare un pezzo di lunghezza $j$ e passare alle lunghezze minori
  4. 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.
dp-f-099 · livello facile · dispensa
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)$?
  1. $-\infty$
  2. $1$
  3. $10$
  4. $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$.
dp-f-100 · livello facile · dispensa
Per il taglio delle aste di lunghezza $n$, la prima PD usa un vettore $v(\ell)$ e la seconda una tabella $v(j,\ell)$. Quanti passi eseguono?
  1. La prima $\Theta(n^2)$, la seconda $\Theta(n^3)$
  2. Entrambe $\Theta(2^{n-1})$
  3. Entrambe $\Theta(n^2)$
  4. La prima $\Theta(n)$, la seconda $\Theta(n^2)$
Spiegazione. La prima calcola $n$ valori, ciascuno con un massimo su al più $n$ termini; la seconda calcola $(n+1)^2$ celle con due termini ciascuna.
dp-f-101 · livello facile · dispensa
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$?
  1. $32$
  2. $7$
  3. $16$
  4. $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.
dp-f-102 · livello facile · dispensa
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?
  1. Tipo $j$ con peso $j$ e profitto $p_j$, copie illimitate, peso totale esattamente $n$
  2. Tipo $j$ con peso $p_j$ e profitto $j$, al più una copia, capacità $n$
  3. Un solo tipo di peso $1$ e profitto $\max_j p_j$, capacità $n$
  4. 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.
dp-f-187 · livello facile · dispensa
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?
  1. Nessuno: ogni schema ha un vettore diverso
  2. Quelli con lo stesso numero di tagli
  3. Quelli con lo stesso pezzo più lungo
  4. 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.
dp-f-188 · livello facile · dispensa
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?
  1. $5$ schemi, profitto massimo $10$
  2. $16$ schemi, profitto massimo $13$
  3. $8$ schemi, profitto massimo $10$
  4. $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$.
dp-f-189 · livello teorema · dispensa
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?
  1. $\Theta(n^2)$, ma pseudo-polinomiale perché dipende da $n$
  2. $\Theta(n^2)$; l'input contiene $n$ prezzi, quindi è polinomiale nella dimensione
  3. $\Theta(2^n)$, come l'enumerazione degli schemi
  4. $\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.
dp-f-190 · livello facile · dispensa
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?
  1. $\Theta(n^2)$, come il primo: $n$ tipi per $n+1$ capacità
  2. $\Theta(n)$
  3. $\Theta(n^3)$
  4. $\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.
dp-f-244 · livello facile · dispensa
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?
  1. $7$
  2. $120$
  3. $16$
  4. $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.
dp-f-245 · livello facile · dispensa
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?
  1. $(0,1,0,0,1)$, profitto $15$
  2. $(1,2,0,0,0)$, profitto $11$
  3. $(2,1,0,0,0)$, profitto $7$
  4. $(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$.
dp-f-246 · livello facile · dispensa
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)$?
  1. $10$
  2. $9$
  3. $13$
  4. $8$
Spiegazione. $v(1)=1$, $v(2)=5$, $v(3)=8$, $v(4)=\max\{1+8,5+5,8+1,9+0\}=10$.
dp-f-247 · livello facile · dispensa
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$?
  1. $16$
  2. $4$
  3. $8$
  4. $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.
dp-f-248 · livello facile · dispensa
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?
  1. Perché ogni lunghezza si usa al più una volta
  2. Perché i prezzi sono interi
  3. Si possono tagliare più pezzi della stessa lunghezza
  4. 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)$.
dp-f-249 · livello facile · dispensa
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$?
  1. $8$
  2. $16$
  3. $10$
  4. $20$
Spiegazione. $4$ tipi per $4$ capacità positive: $16$ aggiornamenti, $\Theta(n^2)$ come la prima PD.
dp-f-295 · livello teorema · dispensa
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?
  1. Perché i profitti sono interi
  2. Perché $n$ si scrive con $\log n$ bit
  3. Perché la ricorrenza ha un solo caso base
  4. 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.
dp-f-296 · livello ipotesi · dispensa
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$?
  1. I profitti crescono con la lunghezza
  2. L'asta va tagliata in due pezzi
  3. Ogni lunghezza si può tagliare quante volte si vuole
  4. Ogni lunghezza al più una volta
Spiegazione. Il pezzo di lunghezza $j$ resta disponibile: l'asta residua è lo stesso problema con lunghezza $\ell-j$.
dp-f-297 · livello teorema · dispensa
In quanti modi si può tagliare un'asta di lunghezza intera $n$ in pezzi di lunghezza intera, se conta l'ordine dei pezzi?
  1. $2^n$
  2. $2^{n-1}$
  3. $n!$
  4. $n^2$
Spiegazione. In ognuno degli $n-1$ punti interni si taglia o no: $2^{n-1}$ schemi, contro $\Theta(n^2)$ passi della PD.
dp-f-298 · livello teorema · dispensa
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ù?
  1. Una soluzione ottima per ogni lunghezza $\ell\le n$
  2. Solo la soluzione per la lunghezza $n$
  3. Tutte le soluzioni ottime
  4. Un bound sul valore ottimo
Spiegazione. Per ogni $\ell$ si ripercorre $s[\ell], s[\ell-s[\ell]],\dots$ fino a $0$.
dp-f-314 · livello facile · dispensa
Asta di lunghezza $4$, profitti $p_1=1$, $p_2=5$, $p_3=8$, $p_4=9$. Quanto vale il profitto massimo $v(4)$?
  1. $10$
  2. $9$
  3. $8$
  4. $11$
Spiegazione. Due pezzi di lunghezza $2$ danno $5+5=10$; $3+1$ dà $9$ e l'asta intera $9$.
dp-f-315 · livello facile · dispensa
Nella PD per il taglio delle aste, perché $v(0)=0$?
  1. Perché $p_0=0$ è un dato
  2. Perché l'asta va tagliata almeno una volta
  3. Perché il profitto massimo è $0$
  4. 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)$?
  1. $13$
  2. $4$
  3. $9$
  4. $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)$?
  1. $25$
  2. $14$
  3. $34$
  4. $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$?
  1. $v(4,11)=27$, $\tilde S=\{2,3\}$
  2. $v(4,11)=25$, $\tilde S=\{2,4\}$
  3. $v(4,11)=34$, $\tilde S=\{1,3,4\}$
  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$?
  1. $v(4,11)=38$, $\tilde S=\{1,3,4\}$
  2. $v(4,11)=29$, $\tilde S=\{2,3,4\}$
  3. $v(4,11)=31$, $\tilde S=\{1,2,3\}$
  4. $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)$?
  1. $36$
  2. $40$
  3. $39$
  4. $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)$?
  1. $29$
  2. $31$
  3. $34$
  4. $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?
  1. $22$ con $x=(2,0,0)$
  2. $24$ con $x=(1,0,1)$
  3. $26$ con $x=(0,0,2)$
  4. $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?
  1. $36$ con $x=(0,0,3)$
  2. $33$ con $x=(3,0,0)$
  3. $29$ con $x=(1,1,1)$
  4. $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)$?
  1. $12$
  2. $8$
  3. $11$
  4. $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)$?
  1. $29$
  2. $26$
  3. $30$
  4. $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)$?
  1. $11$
  2. $5$
  3. $12$
  4. $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)$?
  1. $11$
  2. $29$
  3. $34$
  4. $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}$?
  1. $27$
  2. $26$
  3. $21$
  4. $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}$?
  1. $20$
  2. $22$
  3. $26$
  4. $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?
  1. $3$
  2. $5$
  3. $2$
  4. $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?
  1. $12$
  2. $11$
  3. $14$
  4. $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)$?
  1. $8$
  2. $7$
  3. $9$
  4. $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)$?
  1. $17$
  2. $16$
  3. $22$
  4. $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. $\{1,4,5\}$, valore $21$
  2. $\{1,4,6\}$, valore $21$
  3. $\{1,3,5\}$, valore $17$
  4. $\{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?
  1. $\{2,3,5\}$, valore $18$
  2. $\{2,4,5\}$, valore $21$
  3. $\{2,4,6\}$, valore $19$
  4. $\{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?
  1. $12$
  2. $13$
  3. $20$
  4. $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?
  1. $16$
  2. $23$
  3. $18$
  4. $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. $\{1\}$
  2. $\{2\}$
  3. $\{1,2\}$
  4. $\{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. $\{1,2,3\}$
  2. $\{2,3,4\}$
  3. $\{1,2\}$
  4. $\{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?
  1. $8$
  2. $10$
  3. $7$
  4. $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?
  1. $5$
  2. $13$
  3. $10$
  4. $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)?
  1. $\{2\}$
  2. $\{1\}$
  3. $\{3\}$
  4. $\{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)?
  1. $\{2,3\}$
  2. $\{2,4\}$
  3. $\{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?
  1. $22$
  2. $17$
  3. $16$
  4. $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?
  1. $20$
  2. $21$
  3. $19$
  4. $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. $\{1,2,3\}$
  2. $\{1,2,4\}$
  3. $\{1,2,3,4\}$
  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. $\{1,2,3\}$
  2. $\{1,4\}$
  3. $\{1,3\}$
  4. $\{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)?
  1. $225$
  2. $135$
  3. $275$
  4. $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)?
  1. $610$
  2. $325$
  3. $365$
  4. $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)$?
  1. $180$
  2. $190$
  3. $280$
  4. $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)$?
  1. $265$
  2. $400$
  3. $310$
  4. $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?
  1. $v(5)=310$, lotti nei periodi $1,2,3,4,5$
  2. $v(5)=220$, lotti nei periodi $1,2,5$
  3. $v(5)=375$, lotti nei periodi $1$
  4. $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?
  1. $v(5)=210$, lotti nei periodi $1,4,5$
  2. $v(5)=200$, lotti nei periodi $1,3,5$
  3. $v(5)=280$, lotti nei periodi $1,2,3,4,5$
  4. $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)$?
  1. $31$
  2. $38$
  3. $29$
  4. $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)$?
  1. $23$
  2. $33$
  3. $22$
  4. $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?
  1. $x=(3,3,3)$, costo $42$
  2. $x=(5,4,0)$, costo $40$
  3. $x=(3,6,0)$, costo $34$
  4. $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?
  1. $x=(5,0,4)$, costo $25$
  2. $x=(2,2,5)$, costo $33$
  3. $x=(4,0,5)$, costo $22$
  4. $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)$?
  1. $6$
  2. $10$
  3. $5$
  4. $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)$?
  1. $6$
  2. $4$
  3. $5$
  4. $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$?
  1. $10$
  2. $12$
  3. $9$
  4. $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$?
  1. $5$
  2. $7$
  3. $9$
  4. $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)$?
  1. $22$
  2. $15$
  3. $25$
  4. $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)$?
  1. $10$
  2. $18$
  3. $15$
  4. $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)?
  1. $22$: pezzi $6$
  2. $24$: pezzi $3+3$
  3. $18$: pezzi $1+1+1+1+1+1$
  4. $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)?
  1. $25$: pezzi $1+1+1+1+1$
  2. $22$: pezzi $2+1+1+1$
  3. $15$: pezzi $5$
  4. $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$.