Problema dello Zaino

uni
Questa famiglia di problemi appartiene a quella dei Problema di Programmazione Lineare (PL).
Consiste nell’avere vari oggetti da trasportare, ognuno con un “peso” $p$ (o ingombro) diverso e un valore $v$, ed uno “zaino”, con una certa capienza $C$.
Il problema consiste nel trovare la combinazione di oggetti che permette di portare più peso possibile e quindi “saturare” lo zaino.

Modello bin/intero

$$\{\begin{array}{l}\max v^T\cdot x\\ {\sum }_i{x}_i\le C\\ x_i\in \{0,1\}\text{oppure}{x}_i\in N\end{array}$$

• binario: ogni oggetto può essere portato oppure no, una sola volta: $x$ può essere $0,1$
• intero: ogni oggetto può essere preso quante volte si vuole: $x$ può essere preso $n$ volte ($n\in N$)