Problema dello zaino illimitato (UKP)

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

Definizione 1: Problema dello zaino illimitato

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

il problema dello zaino illimitato (UKP) 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 e il profitto totale di tutte le copie selezionate sia massimo.

Ipotesi

• Facciamo le seguenti ipotesi:

  1. Il peso totale di tutte le copie possibili di tutti gli oggetti (fino al numero massimo che entra nello zaino) supera la capacità dello zaino (altrimenti si potrebbero selezionare tutte le copie). Formalmente:

     \[ \sum_{j \in \mathscr{I}} \hat 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} \]

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. 18 «PD per il problema dello zaino illimitato»; Cap. 27 «PD per il problema del cambio monete»; Cap. 28 «PD per il problema del taglio delle aste»
Esercizi	Esercizio 2.3; Esercizio 9.8; Cap. 18 (5 esercizi)