da mattt » 13/08/2020, 16:02
Mi scuso per non aver inserito tutte le informazioni in mio possesso dall'inizio.
Il problema dello zaino 0/1 consiste nel prendere o meno un oggetto, tenendo conto del profitto massimo e del peso sostenibile dallo zaino:
$sum_(i=1)^(n) Yi * Wi <= C, "con Yi ∈ {0, 1}"$
Il problema dello zaino misto è come il precedente ma permette di prendere solo una parte dell'oggetto, ipotizzando che sia frazionabile:
$sum_(i=1)^(n) Yi * Wi <= C, "con 0 <= Yi <= 1"$
L'ipotesi proposta è "zaino_misto <=p zaino_0_1".
Nell'approccio al problema non capisco come effettuare la riduzione, in quanto passiamo da oggetti frazionabili a oggetti non frazionabili, in teoria:
$R1 ∈ "I1 X {0, 1}", R2 ∈ "I2 X [0, 1]"$, per cui $x ∈ I1 -> f(x) ∈ I2$ (da una istanza x di I1 a una f(x) di I2)
Come posso creare da istanze di oggetti frazionabili istanze di oggetti non frazionabili?
Sarebbe una soluzione corretta dividere una istanza dello zaino misto in due istanze dello zaino 0/1, di cui una rappresenta la parte presa e l'altra la parte non presa?