[Algoritmi] Variazione problema dello zaino

[carmine_c1]

Salve a tutti,
ho un dubbio in merito ad una particolare variazione del problema dello zaino (Programmazione Dinamica).
Ecco la traccia: Dati n oggetti di peso w1,w2,...,wn e valore v1,v2,...,vn ed uno zaino di capacità W (tutti gli input sono >0), trovare il massimo valore di un sottoinsieme degli oggetti il cui peso totale è al massimo W, con la condizione che non possono essere presi due oggetti con indici consecutivi (ovvero gli oggetti i-esimo ed (i+1)-esimo, per i=1,2,...,n-1).
Rispetto al classico problema dello zaino, qui oltre al vincolo di capacità, $sum_{i=0}^n w_ixx_i<=W$, dobbiamo rispettare il vincolo tale che, con indici i La mia domanda è: questo ulteriore vincolo genera dei particolari sottoproblemi e quindi influenza la ricorsione o è semplicemente un vincolo da rispettare durante l'esecuzione dell'algoritmo ed è possibile usare la stessa ricorsione utilizzata per il knapsack 0-1?
Grazie!

[carmine_c1]

Help!!

[apatriarca]

Non ho avuto tempo di pensarci, ma come sono fatti i sottoproblemi del problema dello zaino? Pensi sia possibile modificarli in modo da aggiungere anche il vincolo aggiuntivo? Se sì, come?

[carmine_c1]

Credo di aver risolto.
In sostanza, se l'i-esimo elemento non appartiene alla soluzione ottimale
OPT(i,w) = OPT(i - 1, w).

Se invece l'i-esimo elemento appartiene alla soluzione ottimale
OPT(i, w) = v(i) + OPT(i - 2, w - w(i)) poiché non posso considerare l'oggetto i - 1.

Quindi l'equazione ricorsiva risultante è

OPT(i - 1, w) se w(i) > w
max{OPT(i - 1, w), OPT(i - 2, w - w(i)) + v(i)} altrimenti

[vict85]

Si, è quella. Devi solo ricordarti di fare a parte i primi due indici: in fondo devi solo trovare il massimo tra quei due indici (purché nessuno dei due superi \(w \)).

[smartmouse]

Sapete risolvere il problema dello zaino con la condizione che ogni oggetto può essere preso al massimo 2 volte?

[vict85]

"smartmouse":Sapete risolvere il problema dello zaino con la condizione che ogni oggetto può essere preso al massimo 2 volte?

A occhio penso che sia equivalente a risolvere il problema dello zaino in cui però ogni oggetto è contato due volte.

[smartmouse]

Si, però non essendoci dati concreti, come diventerebbe in questo caso il sistema postato più sopra da carmine_c?
In sostanza è proprio questo sistema la risposta a quesiti del genere?

[carmine_c1]

Allora questo è il caso del bounded knapsack, dove un oggetto può essere preso x volte con 0 <= x <= b.
Nel tuo caso b = 2, quindi il sistema è il seguente:

se l'i-esimo elemento non appartiene alla soluzione ottimale
OPT(i,w) = OPT(i - 1, w)

se l'i-esimo elemento appartiene alla soluzione ottimale
OPT(i,w) = v(i) + OPT(i, w - w(i)) in questo caso non devo decrementare l'i-esimo oggetto perché posso sceglierlo di nuovo (verrà decrementata solo quando raggiungeremo il limite, che in questo caso è 2)

Il sistema risultante è
OPT(i - 1, w) se w(i) > w
max{OPT(i - 1, w), OPT(i, w - w(i)) + v(i)} altrimenti