Problema dello zaino a scelta multipla (MCKP)

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

Definizione 1: Problema dello zaino a scelta multipla

Dati:

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

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

3. una partizione dell'insieme degli oggetti in \(q \in \Z_{\ge 2}\) classi,

4. per ogni classe \(h \in \{1,2,\dots,q\}\), il sottoinsieme \(\mathscr{J}_h \subseteq \mathscr{I}\) degli oggetti di quella classe,

5. 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 a scelta multipla (MCKP) chiede di decidere quali oggetti inserire nello zaino, in modo che da ogni classe sia selezionato esattamente un oggetto, che il peso totale degli oggetti selezionati non superi la capacità dello zaino e che il profitto totale degli oggetti selezionati sia massimo.

Ipotesi

• Facciamo le seguenti ipotesi:

  1. Ogni classe contiene almeno un oggetto (altrimenti selezionare esattamente un oggetto da ogni classe è impossibile). Formalmente:

     \[ \mathscr{J}_h \neq \emptyset \qquad \forall\, h\in\{1,\dots,q\}. \]

  2. L'istanza è ammissibile, ossia esiste almeno una scelta di esattamente un oggetto per classe che entra nello zaino. Una condizione necessaria e sufficiente (e facile da verificare) è:

     \[ \sum_{h=1}^{q}\ \min_{j\in \mathscr{J}_h} w_j \;\le\; c. \]

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. 21 «PD per il problema dello zaino a scelta multipla»
Esercizi	Esercizio 2.5; Esercizio 9.11; Esercizio 16.5; Cap. 21 (5 esercizi)