2.4 Il problema dello zaino limitato¶
Parte 1 · Problemi di ottimizzazione combinatoria · Capitolo 2 · Capitolo 2: Problemi di zaino · Dispensa, volume 1 (PDF) · Slide · Esercizi: Problemi di zaino · App: Forza bruta sul problema dello zaino 0/1
Definizione 2.4: problema dello zaino limitato
Dati:
-
uno zaino di capacità \(c \in \Z_{\ge 1}\),
-
un insieme \(\mathscr{I} = \{1,2,\dots,n\}\) di \(n\) oggetti,
-
per ogni oggetto \(j \in \mathscr{I}\), un profitto \(p_j \in \Z_{\ge 1}\), un peso \(w_j \in \Z_{\ge 1}\) e un numero di copie disponibili \(b_j \in \Z_{\ge 1}\),
il problema dello zaino limitato (BKP) chiede di decidere quante copie di ogni oggetto inserire nello zaino, in modo che il peso totale di tutte le copie selezionate non superi la capacità dello zaino, che nessun oggetto sia preso più volte delle sue copie disponibili e che il profitto totale di tutte le copie selezionate sia massimo.
-
Un'istanza del BKP è specificata da:
-
due numeri interi:
-
il numero di oggetti \(n \in \Z_{\ge 1}\),
-
la capacità dello zaino \(c \in \Z_{\ge 1}\),
-
-
tre vettori di numeri interi di lunghezza \(n\):
-
\(\vet{p} \in \Z_{\ge 1}^n\), che contiene i profitti degli oggetti,
-
\(\vet{w} \in \Z_{\ge 1}^n\), che contiene i pesi degli oggetti,
-
\(\vet{b} \in \Z_{\ge 1}^n\), che contiene il numero di copie disponibili di ogni oggetto.
-
-
-
Data un'istanza del BKP, definiamo l'insieme esteso degli oggetti come
\[\begin{equation*} \label{ExtSet} \hat{\mathscr{I}} = \big\{\, (j,k) : j \in \mathscr{I},~ k \in \{1,2,\dots,b_j\} \,\big\}, \tag{2.3} \end{equation*}\]dove ogni coppia \((j,k)\) rappresenta la \(k\)-esima copia disponibile dell'oggetto \(j\). La cardinalità dell'insieme esteso degli oggetti è
\[ |\hat{\mathscr{I}}| = \sum_{j \in \mathscr{I}} b_j. \] -
Una soluzione ammissibile del BKP è un sottoinsieme di oggetti
\[ S \subseteq \hat{\mathscr{I}} \]tale che il peso totale degli oggetti selezionati non supera la capacità dello zaino, ossia
\[ \sum_{(j,k)\in S} w_j \le c . \]Di conseguenza, il BKP si può enunciare in modo equivalente come il problema di selezionare un sottoinsieme dell'insieme esteso degli oggetti il cui peso totale rispetta la capacità dello zaino e il cui profitto totale è massimo.
Data un'istanza del BKP, il BKP si può enunciare formalmente come:
\[\begin{equation*} \label{BKP} \tilde{S}\in \arg\max_{S \subseteq \hat{\mathscr{I}} } \left\{~~ \sum_{(j,k) \in S} p_j \;:\; \sum_{(j,k) \in S} w_j \le c ~~\right\}. \tag{2.4} \end{equation*}\]
Esempio 2.3: istanza del BKP
Consideriamo uno zaino di capacità \(c = 9\) e un insieme \(\mathscr{I} = \{1,2,3,4,5,6\}\) di \(6\) oggetti (\(n = 6\)), con i seguenti profitti, pesi e copie disponibili:
| Oggetti | \(j = 1\) | \(j = 2\) | \(j = 3\) | \(j = 4\) | \(j = 5\) | \(j = 6\) | |
|---|---|---|---|---|---|---|---|
| Profitti | \(p_j\) | \(6\) | \(5\) | \(8\) | \(9\) | \(6\) | \(7\) |
| Pesi | \(w_j\) | \(2\) | \(3\) | \(6\) | \(7\) | \(5\) | \(9\) |
| Copie disponibili | \(b_j\) | \(2\) | \(2\) | \(1\) | \(1\) | \(1\) | \(1\) |
L'insieme esteso degli oggetti è:
Ogni copia \((j,k)\) ha profitto \(p_j\) e peso \(w_j\).
| Etichetta della copia | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| \((j,k)\) | \((1,1)\) | \((1,2)\) | \((2,1)\) | \((2,2)\) | \((3,1)\) | \((4,1)\) | \((5,1)\) | \((6,1)\) |
| Profitto \(p_j\) | \(6\) | \(6\) | \(5\) | \(5\) | \(8\) | \(9\) | \(6\) | \(7\) |
| Peso \(w_j\) | \(2\) | \(2\) | \(3\) | \(3\) | \(6\) | \(7\) | \(5\) | \(9\) |
Il disegno mostra una soluzione ottima: le due copie dell'oggetto \(1\) e la copia dell'oggetto \(5\), con peso \(2+2+5=9\) e profitto \(6+6+6=18\).
2.4.1 Ipotesi¶
-
Facciamo le seguenti ipotesi:
-
Il peso totale di tutte le copie disponibili di tutti gli oggetti supera la capacità dello zaino (altrimenti si potrebbero selezionare tutte le copie). Formalmente:
\[ \sum_{j \in \mathscr{I}} b_j \, w_j > c \] -
Ogni oggetto, da solo, entra nello zaino (altrimenti non può essere selezionato). Formalmente:
\[ w_j \le c, \qquad \forall j \in \mathscr{I} \] -
Il peso totale di tutte le copie disponibili di un singolo oggetto non supera la capacità dello zaino (altrimenti quell'oggetto non potrebbe mai essere preso nel numero massimo di copie consentito). Formalmente:
\[ b_j \, w_j \le c, \qquad \forall j \in \mathscr{I} \]
-