Problema di knapsack binario (problema dello zaino)

[AndreaNobili1]

Ragazzi,
aiuto sono disperato...dovrei tentare un appello straordinario di ricerca operativa tra qualche giorno...il corso è stato l'anno scorso e non ho potuto seguirlo quasi per niente purtroppo (ero impegnato con altri 3 corsi + un progetto)...ed ho proprio bisogno del vostro aiuto...non saprei proprio a chi rivolgermi ora...

Bando alle ciance...l'esercizio dice:

Si risolva il seguente problema di knapsack-{0,1} (quindi knapsack binario):

max{ 42*X1 + 11*X2 + 15*X3 + 2*X4 : 9*X1 + 2*X2 + 7*X3 + X4 <= 10, X appartiene a {0,1}^4}

Si illustrino chiaramente, su di un albero di enumerazione, i sottoproblemi ed il loro ordine di visita, i relativi upper bound e le variabili di branching.

Leggendo un po' online ho più o meno capito di cosa si tratta ma non ho la minima idea di come farlo...sò che dovvrebbe essere una cosa molto semplice e sopratutto molto meccanica

C'è qualche anima pia che mi sà spiegare passo passo ciò che dovrei fare basandosi su questo esempio?

Grazie mille
Andrea

[hamming_burst]

Ciao, questa rappresentazione del problema è legata alla programmazione lineare scommetto

Io lo conosco tramite risoluzione con programmazione dinamica. Ma il problema è lo stesso.

Se ho capito bene, devi crearti l'albero delle scelte. Non è complicato è solo lunga da scrivere i sotto-problemi; prima cosa ti conviene suddividere e formalizzare il problema:

- $4$ oggetti
- $p={42;11;15;2}$ profitto
- $v={9;2;7;1}$ volume
- $K=10$ capacità

Adesso devi individuare una relazione di ordinamento sui nodi dell'albero.

Quello che ti consiglio è usare la rappresentazione del problema con l'equazione di ricorsione fatto con programmazione dinamica.
Questa equazione risolve esattamente tutti i sotto-problemi, e il suo formalismo ti aiuta a capire qual è questa relazione.

es: all'altezza i-esima si avrà la sottrazione del volume dell'oggetto $j$ alla capacità, cioè $K-v_j$ e se questa è massima si sommerà il profitto dell'oggetto.

Se segui l'equazione di ricorsione e lo dirami, sei a buon punto.

Per la limitazione inferiore al problema, ci sono tecniche apposite, direi (si trova su qualunque buon libro) che in questo caso si usa il valore dei dati in ingesso (anche con "gli eventi contabili", i confronti, ci si può pansare) dire che è legata alla capacità dello zaino e dal numero degli oggetti, anche se dipende dai valori dei volumi, e non prenderla come oro, penso sia $Omega(nK)$ anche se è la complessità dell'algoritmo dinamico.

Ti ho dato solo un'idea, risolvere l'albero delle decisioni è davvero lunga da scrivere