Problema degli zaini multipli (MKP)

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

Definizione 1: Problema degli zaini multipli

Dati:

1. \(m \in \Z_{\ge 1}\) zaini,

2. per ogni zaino \(k \in \underbrace{\{1,2,\dots,m\}}_{=\mathscr{K}}\), una capacità \(c_k \in \Z_{\ge 1}\),

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

4. 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.

Ipotesi

• Facciamo le seguenti ipotesi:

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

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

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. 24 «PD per il problema degli zaini multipli»
Esercizi	Esercizio 2.4; Esercizio 9.10; Cap. 24 (5 esercizi)