Vai al contenuto

Problemi di zaino

Parte 1 · Problemi di ottimizzazione combinatoria · Capitolo 2 · Dispensa, volume 1 (PDF) · Slide · Esercizi: Problemi di zaino · App: Forza bruta sul problema dello zaino 0/1

Prerequisiti

Obiettivi

Al termine di questo capitolo saremo in grado di:

  • enunciare la definizione del problema dello zaino 0/1 e delle sue varianti, con istanze e soluzioni ammissibili;

  • spiegare le ipotesi sui dati e perché si possono fare senza perdita di generalità;

  • contare le soluzioni candidate e le soluzioni ammissibili di una piccola istanza;

  • trovare a mano una soluzione ammissibile e calcolare un semplice bound duale combinatorio;

  • distinguere le varianti: copie degli oggetti, più risorse, più zaini, classi di oggetti.

2.1 Panoramica della famiglia

  • I problemi di zaino hanno gli stessi dati: un insieme \(\mathscr{I} = \{1,2,\dots,n\}\) di \(n\) oggetti, per ogni oggetto \(j \in \mathscr{I}\) un peso \(w_j \in \Z_{\ge 1}\) e un profitto \(p_j \in \Z_{\ge 1}\), e uno o più zaini con una capacità in \(\Z_{\ge 1}\).

  • Una soluzione decide quali oggetti selezionare, o quante copie di ogni oggetto: il peso totale degli oggetti selezionati non deve superare la capacità dello zaino che li riceve.

  • L'obiettivo è massimizzare il profitto totale degli oggetti selezionati.

Un problema di zaino seleziona oggetti di profitto totale massimo il cui peso totale rispetta le capacità. I membri della famiglia differiscono nel numero di copie degli oggetti, nel numero di capacità e di zaini, e nelle classi in cui gli oggetti sono raggruppati.

  • La tabella elenca i membri della famiglia, con la sezione che definisce ciascuno di essi.
Problema Sigla Differenza rispetto al KP Sezione
problema dello zaino 0/1 KP una copia di ogni oggetto, uno zaino 2.2
problema del subset sum SSP \(p_j = w_j\), peso totale esattamente uguale a \(c\) 2.3
problema dello zaino limitato BKP al più \(b_j\) copie dell'oggetto \(j\) 2.4
problema dello zaino illimitato UKP un numero illimitato di copie di ogni oggetto 2.5
problema dello zaino multidimensionale MDKP \(k\) capacità \(c_d\) e pesi \(w_{dj}\) 2.6
problema degli zaini multipli MKP \(m\) zaini con capacità \(c_k\) 2.7
problema dello zaino a scelta multipla MCKP classi \(\mathscr{J}_h\), esattamente un oggetto per classe 2.8
problema dello zaino con setup KPS classi \(\mathscr{J}_h\) con costi di setup \(f_h\) e pesi di setup \(s_h\) 2.9

2.1.1 Le varianti in breve

  • Ogni problema della famiglia è illustrato su una piccola istanza, nella sua sezione della tabella precedente e con la notazione di quella sezione.

  • La tabella riporta, per queste istanze, il numero di soluzioni candidate, il numero di soluzioni ammissibili e il valore ottimo, calcolati per enumerazione.

  • Nel BKP e nell'UKP una soluzione candidata è il vettore dei numeri di copie di ogni oggetto, così che copie identiche non sono contate due volte.

  • La soluzione ottima non è sempre unica: l'MKP, l'MCKP e il KPS hanno più soluzioni ottime con lo stesso valore, e nel SSP tre sottoinsiemi raggiungono il valore obiettivo.

Variante Soluzioni candidate Numero Ammissibili Ottimo Soluzioni ottime
KP sottoinsiemi di \(6\) oggetti \(64\) \(13\) \(15\) \(\{1,4\}\)
SSP sottoinsiemi di \(6\) oggetti \(64\) \(3\) sì \(\{6\}\), \(\{1,4\}\), \(\{2,3\}\)
BKP copie \(x_j \le b_j\) \(144\) \(18\) \(18\) due copie dell'oggetto \(1\) e l'oggetto \(5\)
UKP copie \(x_j \le \hat b_j\) \(320\) \(22\) \(24\) quattro copie dell'oggetto \(1\)
MDKP sottoinsiemi di \(4\) oggetti \(16\) \(9\) \(14\) \(\{3,4\}\)
MKP ogni oggetto in uno zaino o in nessuno \(243\) \(109\) \(30\) \((S_1,S_2) = (\{1,2\},\{4,5\})\), \((\{2,4\},\{1,5\})\), \((\{4,5\},\{1,2\})\)
MCKP un oggetto per classe \(8\) \(3\) \(17\) \(\{1,4,5\}\), \(\{2,3,5\}\)
KPS sottoinsiemi di \(6\) oggetti \(64\) \(40\) \(16\) \(\{1,2,3\}\), \(\{4,5,6\}\), \(\{1,2,3,6\}\)
  • Nell'MCKP solo \(3\) delle \(8\) scelte di un oggetto per classe entrano nello zaino: la condizione di ammissibilità fra le ipotesi della Sezione 2.8 non è una formalità.

  • Panoramica

    Panoramica della famiglia · Le varianti in breve

    Apri

  • 2.2 Il problema dello zaino 0/1

    Contare le soluzioni, una prima soluzione e un bound semplice

    Apri

  • 2.3 Il problema del subset sum

    Apri

  • 2.4 Il problema dello zaino limitato

    Apri

  • 2.5 Il problema dello zaino illimitato

    Apri

  • 2.6 Il problema dello zaino multidimensionale

    Apri

  • 2.7 Il problema degli zaini multipli

    Apri

  • 2.8 Il problema dello zaino a scelta multipla

    Apri

  • 2.9 Il problema dello zaino con setup

    Osservazioni · Errori tipici · In sintesi

    Apri

Avanti: 2.2 Il problema dello zaino 0/1

Esercizi su questo capitolo: Problemi di zaino

Approfondimento: che cosa fa il corso su questo problema

Nel laboratorio interattivo: Forza bruta sul problema dello zaino 0/1.