2.3 Il problema del subset sum¶
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.3: problema del subset sum
Dati:
-
un valore obiettivo \(c \in \Z_{\ge 1}\),
-
un insieme \(\mathscr{I} = \{1,2,\dots,n\}\) di \(n\) oggetti,
-
per ogni oggetto \(j \in \mathscr{I}\), un peso \(w_j \in \Z_{\ge 1}\),
il problema del subset sum (SSP) chiede se esiste un sottoinsieme di oggetti il cui peso totale è esattamente uguale al valore obiettivo \(c\).
-
Un'istanza del SSP è specificata da:
-
due numeri interi:
-
il numero di oggetti \(n \in \Z_{\ge 1}\),
-
il valore obiettivo \(c \in \Z_{\ge 1}\),
-
-
un vettore di numeri interi di lunghezza \(n\):
- \(\vet{w} \in \Z_{\ge 1}^n\), che contiene i pesi degli oggetti.
-
-
Una soluzione ammissibile del SSP è un sottoinsieme di oggetti
\[ S \subseteq \mathscr{I} \]tale che il peso totale degli oggetti selezionati è esattamente uguale al valore obiettivo, ossia
\[ \sum_{j\in S} w_j = c . \]Di conseguenza, il SSP si può enunciare in modo equivalente come il problema di selezionare un sottoinsieme di oggetti il cui peso totale coincide esattamente con il valore obiettivo.
Data un'istanza del SSP, il SSP si può enunciare formalmente come:
\[\begin{equation*} \label{SSP} \text{trovare } S \subseteq \mathscr{I} \quad \text{tale che} \quad \sum_{j \in S} w_j = c . \tag{2.2} \end{equation*}\]
Esempio 2.2: istanza del SSP
Consideriamo un valore obiettivo \(c = 9\) e un insieme \(\mathscr{I} = \{1,2,3,4,5,6\}\) di \(6\) oggetti (\(n = 6\)), con i seguenti pesi:
| Oggetti | \(j = 1\) | \(j = 2\) | \(j = 3\) | \(j = 4\) | \(j = 5\) | \(j = 6\) | |
|---|---|---|---|---|---|---|---|
| Pesi | \(w_j\) | \(2\) | \(3\) | \(6\) | \(7\) | \(5\) | \(9\) |
Per esempio, il sottoinsieme \(S=\{1,4\}\) è ammissibile poiché \(w_1+w_4=2+7=9\). Anche il sottoinsieme \(S=\{6\}\) è ammissibile poiché \(w_6=9\). Il disegno mostra i tre sottoinsiemi i cui pesi riempiono esattamente la scatola di lunghezza \(c=9\): \(\{1,4\}\), \(\{6\}\) e \(\{2,3\}\).
-
Il SSP non è un problema di ottimizzazione, poiché la sua risposta è sì oppure no. Tuttavia, si può risolvere usando un problema di ottimizzazione.
-
Un'istanza del SSP si può risolvere come un'istanza del KP ponendo il profitto di ogni oggetto uguale al suo peso, ossia
\[ p_j = w_j, \qquad \forall j\in \mathscr{I}. \]In questo caso, risolviamo il seguente KP:
\[\begin{equation*} \tilde{S}\in \arg\max_{S \subseteq \mathscr{I}} \left\{~~ \sum_{j \in S} w_j \;\;:\;\; \sum_{j \in S} w_j \le c ~~\right\}. \end{equation*}\]Se \(\sum_{j\in \tilde{S}} w_j = c\), la risposta al SSP è sì; altrimenti, se \(\sum_{j\in \tilde{S}} w_j < c\), la risposta è no.
2.3.1 Ipotesi¶
-
Facciamo le seguenti ipotesi:
-
Il peso totale di tutti gli oggetti è almeno pari al valore obiettivo (altrimenti non può esistere alcun sottoinsieme ammissibile). Formalmente:
\[ \sum_{j \in \mathscr{I}} w_j \ge c \] -
Il peso di ogni oggetto non supera il valore obiettivo (altrimenti l'oggetto non può appartenere ad alcun sottoinsieme ammissibile). Formalmente:
\[ w_j \le c,~~~~ \forall j \in \mathscr{I} \]
-