2.2 Il problema dello zaino 0/1

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.1: problema dello zaino 0/1

Dati:

1. uno zaino di capacità \(c \in \Z_{\ge 1}\),

2. un insieme \(\mathscr{I} = \{1,2,\dots,n\}\) di \(n\) oggetti,

3. 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 dello zaino 0/1 (KP) chiede di decidere quali oggetti inserire nello zaino, in modo che il peso totale degli oggetti selezionati non superi la capacità dello zaino e il profitto totale degli oggetti selezionati sia massimo.

• Un'istanza del KP è specificata da:

  1. due numeri interi:

     • il numero di oggetti \(n \in \Z_{\ge 1}\),

     • la capacità dello zaino \(c \in \Z_{\ge 1}\),

  2. due 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.

• Una soluzione ammissibile del KP è un sottoinsieme di oggetti

  \[ S \subseteq \mathscr{I} \]

  tale che il peso totale degli oggetti selezionati non supera la capacità dello zaino, ossia

  \[ \sum_{j\in S} w_j \le c . \]

  Di conseguenza, il KP si può enunciare in modo equivalente come il problema di selezionare un sottoinsieme di oggetti il cui peso totale rispetta la capacità dello zaino e il cui profitto totale è massimo.

  Data un'istanza del KP, il KP si può enunciare formalmente come:

  \[\begin{equation*} \label{KP} \tilde{S}\in \arg\max_{S \subseteq \mathscr{I}} \left\{~~ \sum_{j \in S} p_j \;\;:\;\; \sum_{j \in S} w_j \le c ~~\right\}. \tag{2.1} \end{equation*}\]

Esempio 2.1: istanza del KP

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 e pesi:

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\)

Nel disegno, lo zaino è una scatola di lunghezza \(c=9\) e ogni oggetto è un blocco di lunghezza \(w_j\). Gli oggetti \(1\) e \(4\) riempiono lo zaino, con peso \(9\) e profitto \(15\); gli altri oggetti restano fuori (tratteggiati).

Chiamiamo questa istanza del KP Esempio 2.1: è l'istanza di riferimento del capitolo.

2.2.1 Ipotesi

• Facciamo le seguenti ipotesi:

  1. Il peso totale di tutti gli oggetti supera la capacità dello zaino (altrimenti si potrebbero selezionare tutti gli oggetti). Formalmente:

     \[ \sum_{j \in \mathscr{I}} w_j > c \]

  2. Ogni oggetto, da solo, entra nello zaino (altrimenti non può essere selezionato). Formalmente:

     \[ w_j \le c,~~~~ \forall j \in \mathscr{I} \]

2.2.2 Contare le soluzioni, una prima soluzione e un bound semplice

• Soluzioni candidate. Ogni sottoinsieme di \(\mathscr{I}\) è una soluzione candidata, quindi ce ne sono \(2^n\) (Capitolo 1 «Problemi di ottimizzazione combinatoria»). Per l'Esempio 2.1 abbiamo \(2^6 = 64\).

• Soluzioni ammissibili. I tre oggetti più leggeri pesano \(2+3+5 = 10 > 9\), quindi nessun sottoinsieme con tre o più oggetti è ammissibile. Le soluzioni ammissibili sono l'insieme vuoto, i \(6\) singoletti e le \(6\) coppie della tabella seguente: \(13\) soluzioni su \(64\).

coppia \(S\)	\(\{1,2\}\)	\(\{1,3\}\)	\(\{1,4\}\)	\(\{1,5\}\)	\(\{2,3\}\)	\(\{2,5\}\)
peso	\(5\)	\(8\)	\(9\)	\(7\)	\(9\)	\(8\)
profitto	\(11\)	\(14\)	\(\mathbf{15}\)	\(12\)	\(13\)	\(11\)

• Una prima soluzione, a occhio. L'oggetto \(4\) ha il profitto massimo (\(9\), peso \(7\)). La capacità residua \(9-7=2\) basta per l'oggetto \(1\) (peso \(2\), profitto \(6\)). Il sottoinsieme \(\{1,4\}\) ha peso \(9\) e profitto \(15\): è un bound primale, \(\LB = 15 \le z(I)\).

Osservazione 2.2: bound di cardinalità

Sia \(\bar k\) il più grande intero tale che i \(\bar k\) oggetti più leggeri pesano al più \(c\). Ogni sottoinsieme ammissibile ha al più \(\bar k\) oggetti, quindi \(z(I)\) è al più la somma dei \(\bar k\) profitti più grandi.

Dimostrazione

Un sottoinsieme con \(k\) oggetti pesa almeno quanto i \(k\) oggetti più leggeri. Se \(k > \bar k\), i \(k\) oggetti più leggeri pesano più di \(c\), quindi il sottoinsieme non è ammissibile. Il profitto di un sottoinsieme con al più \(\bar k\) oggetti è al più la somma dei \(\bar k\) profitti più grandi. □

• Un primo bound duale. Nell'Esempio 2.1 abbiamo \(\bar k = 2\), poiché \(2+3 = 5 \le 9\) e \(2+3+5 = 10 > 9\). I due profitti più grandi sono \(9\) e \(8\), quindi \(\UB = 17\). La somma di tutti i profitti, \(41\), è un bound duale molto più debole.

• Il gap. Abbiamo \(15 \le z(I) \le 17\): il gap assoluto è \(2\) e il gap relativo è \(\tfrac{2}{15}\). Elencando i \(13\) sottoinsiemi ammissibili si vede che \(\{1,4\}\) è l'unica soluzione ottima e \(z(I) = 15\); per istanze più grandi servono bound più forti, che vengono dai rilassamenti (modulo Programmazione lineare intera, Capitolo 2 «Bound primali e duali»).

---

Avanti: 2.3 Il problema del subset sum