Riduzione polinomiale dal problema dello zaino misto (NP-hard)

[mattt]

Ho il seguente esercizio: Progettare una riduzione polinomiale dal problema dello zaino misto al problema dello zaino 0/1.
Come dimostro che un problema può essere ricondotto all'altro?

[vict85]

Moderatore: vict85

Il problema è più informatico che algebrico/logico, sposto lì.

In ogni caso il Regolamento prevede dei tentativi da parte tua. Qualche idea? Personalmente non mi ricordo le due formulazioni di quei problemi, le ho viste molto tempo fa, immagino potrebbe essere utile se le scrivessi.

[mattt]

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?