Problema del subset sum (SSP)

Catalogo dei problemi di ottimizzazione combinatoria · Problemi di zaino · Catalogo (PDF)

Definizione 1: Problema del subset sum

Dati:

1. un valore obiettivo \(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 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\).

Ipotesi

• Facciamo le seguenti ipotesi:

  1. 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 \]

  2. 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} \]

Che cosa fa il corso su questo problema

Tecnica	Dove
Definizione	Cap. 2 «Problemi di zaino»
Formulazioni	Cap. 9 «Formulazioni dei problemi di zaino»
Programmazione dinamica	Cap. 16 «Principi della programmazione dinamica»; Cap. 20 «PD per il problema del subset sum»
Esercizi	Esercizio 2.2; Esercizio 9.6; Esercizio 16.2; Cap. 20 (5 esercizi)