Problema dello zaino limitato (BKP)

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

Definizione 1: Problema dello zaino limitato

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}\), un peso \(w_j \in \Z_{\ge 1}\) e un numero di copie disponibili \(b_j \in \Z_{\ge 1}\),

il problema dello zaino limitato (BKP) chiede di decidere quante copie di ogni oggetto inserire nello zaino, in modo che il peso totale di tutte le copie selezionate non superi la capacità dello zaino, che nessun oggetto sia preso più volte delle sue copie disponibili e che il profitto totale di tutte le copie selezionate sia massimo.

Ipotesi

• Facciamo le seguenti ipotesi:

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

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

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

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

  3. Il peso totale di tutte le copie disponibili di un singolo oggetto non supera la capacità dello zaino (altrimenti quell'oggetto non potrebbe mai essere preso nel numero massimo di copie consentito). Formalmente:

     \[ b_j \, w_j \le c, \qquad \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. 19 «PD per il problema dello zaino limitato»
Esercizi	Esercizio 2.3; Esercizio 9.7; Cap. 19 (5 esercizi)