2.7 Il problema degli zaini multipli¶
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.7: problema degli zaini multipli
Dati:
-
\(m \in \Z_{\ge 1}\) zaini,
-
per ogni zaino \(k \in \underbrace{\{1,2,\dots,m\}}_{=\mathscr{K}}\), una capacità \(c_k \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}\) e un peso \(w_{j} \in \Z_{\ge 1}\),
il problema degli zaini multipli (MKP) chiede di decidere quali oggetti inserire in ogni zaino, in modo che in ogni zaino il peso totale degli oggetti assegnati non superi la sua capacità e il profitto totale degli oggetti selezionati sia massimo.
-
Un'istanza dell'MKP è specificata da:
-
due numeri interi:
-
il numero di oggetti \(n \in \Z_{\ge 1}\),
-
il numero di zaini \(m \in \Z_{\ge 1}\),
-
-
un vettore di numeri interi di lunghezza \(n\):
- \(\vet{p} \in \Z_{\ge 1}^n\), che contiene i profitti degli oggetti,
-
un vettore di numeri interi di lunghezza \(n\):
- \(\vet{w} \in \Z_{\ge 1}^n\), che contiene i pesi degli oggetti,
-
un vettore di numeri interi di lunghezza \(m\):
- \(\vet{c} \in \Z_{\ge 1}^m\), che contiene le capacità degli zaini.
-
-
Una soluzione ammissibile dell'MKP è una famiglia di sottoinsiemi di oggetti
\[ \mathcal{S}=\{S_k\}_{k\in \mathscr{K}}, \qquad S_k \subseteq \mathscr{I} \ \ \text{per ogni } k\in \mathscr{K}, \]tale che:
-
(i) ogni oggetto è assegnato ad al più uno zaino, ossia
\[ S_k \cap S_{k'}=\emptyset \quad \text{per ogni } k,k'\in \mathscr{K}\ \text{con } k\neq k'; \] -
(ii) il peso totale degli oggetti assegnati a ogni zaino rispetta la sua capacità, ossia
\[ \sum_{j\in S_k} w_j \le c_k \quad \text{per ogni } k\in \mathscr{K}. \]
Di conseguenza, l'MKP si può enunciare in modo equivalente come il problema di selezionare sottoinsiemi di oggetti a due a due disgiunti, uno per ogni zaino, in modo che ogni capacità sia rispettata e il profitto totale sia massimo.
Data un'istanza dell'MKP, l'MKP si può enunciare formalmente come:
\[\begin{equation*} \label{MKP} \tilde{\mathcal{S}} \in \argmax_{\mathcal{S}=\{S_k\}_{k\in \mathscr{K}}} \left\{ \sum_{k\in \mathscr{K}} \ \sum_{j\in S_k} p_j \;:\; \begin{array}{l} S_k \subseteq \mathscr{I} \quad \forall\, k\in \mathscr{K},\\[6pt] S_k \cap S_{k'}=\emptyset \quad \forall\, k,k'\in \mathscr{K}\ \text{con } k\neq k',\\[10pt] \displaystyle \sum_{j\in S_k} w_j \le c_k \quad \forall\, k\in \mathscr{K} \end{array} \right\}. \tag{2.9} \end{equation*}\] -
Esempio 2.6: istanza dell'MKP
Consideriamo \(m = 2\) zaini con capacità \(c_1 = 10\) e \(c_2 = 12\), e un insieme \(\mathscr{I} = \{1,2,3,4,5\}\) di \(5\) oggetti (\(n = 5\)), con i seguenti profitti e pesi:
| Oggetti | \(j = 1\) | \(j = 2\) | \(j = 3\) | \(j = 4\) | \(j = 5\) | |
|---|---|---|---|---|---|---|
| Profitti | \(p_j\) | \(6\) | \(8\) | \(5\) | \(7\) | \(9\) |
| Pesi | \(w_j\) | \(4\) | \(6\) | \(5\) | \(3\) | \(7\) |
Il disegno mostra una soluzione ottima: \(S_1=\{1,2\}\) nello zaino \(1\) e \(S_2=\{4,5\}\) nello zaino \(2\), con profitto totale \(14+16=30\); l'oggetto \(3\) resta fuori.
2.7.1 Ipotesi¶
-
Facciamo le seguenti ipotesi:
-
L'insieme di tutti gli oggetti non entra nel complesso degli zaini (altrimenti selezionare tutti gli oggetti è ammissibile e ottimo). Formalmente,
\[ \sum_{j\in \mathscr{I}} w_j \;>\; \sum_{k\in \mathscr{K}} c_k . \] -
Ogni oggetto, da solo, entra in (almeno) uno zaino (altrimenti non può mai essere selezionato). Formalmente,
\[ \forall\, j\in \mathscr{I}\quad \exists\, k\in \mathscr{K}\ \text{tale che}\ w_j \le c_k . \]
-