Si supponga di avere uno zaino (knapsack) di capacità C e n oggetti ognuno dei quali ha un peso Pi e un’utilità Ui (o valore). Il problema consiste nel riempire lo zaino,  rispettandone la capacità, con gli oggetti che danno la maggiore utilità complessiva.

Il problema dello zaino può essere formulato come modello di programmazione lineare binaria booleana

     max                    

Nella formulazione del problema si ipotizza, inoltre, che alcuni oggetti abbiano un peso inferiore alla capacità dello zaino e che la somma dei pesi di tutti gli oggetti sia superiore alla capienza stessa.

Il problema dello zaino può essere risolto mediante tecniche euristiche o approssimate e tecniche esatte.

Algoritmo euristico:inserire nello zaino gli oggetti in ordine di utilità specifica decrescente, ricercando cioè l’oggetto con utilità specifica “max “ e inserirlo nello zaino, inserire nello spazio residuo l’oggetto con utilità specifica immediatamente più piccola e ciò fino ad esaurire la capacità.

La soluzione determinata non è, però, quella ottimale ma è una approssimazione.

                                                                             Esempio:

    Riordinando gli oggetti in ordine decrescente del rapporto (valore/peso) con il foglio elettronico Excel ,si osserva che si può trasportare soltanto l'oggetto C. La soluzione ottimale secondo questo metodo  è,quindi, approssimata.      

Applicando, invece,  il metodo branch-and-bound

• si ordinano  gli oggetti secondo valori specifici decrescenti;
• si crea un albero binario, dove man mano che si procede dalla radice alle foglie vengono fissate alcune variabili( 1 significa prendere l'oggetto; 0 significa escludere l'oggetto);
• si determina l'Upper bound ,selezionando gli oggetti con le variabili a 1 ed escludendo quelli con variabili a 0, e ipotizzando che gli oggetti siano frazionabili, si determina l'elemento critico

L'Upper Bound si calcola:

essendo:

= frazione dell' elemento critico   c = capacitá Knapsack = dimensioni degli elementi = valori degli elementi

Il problema diventa:

Z=26 X₁+43X₂+32X₃+12X₄

i=1,2,3,4,,..

 Siccome l’oggetto C ha il migliore rapporto (peso/valore) si generano due sotto problemi: di portare l'oggetto C o di non portarlo

 Nodo 1

   x₁=1

z=26+43x₂+32x₃+12x₄

22x₂+18x₃+7x₄<=17                           

CBUB(1) = 26 + 43* (30-13)/22 ;   arrotondando CBUB (1) = 59

Nodo 2 

  x₁=0

z=43x₂+32x₃+12x₄

22x₂+18x₃+7x₄<=30                    

CBUB (0) arrotondando CBUB (0) = 57

E' più conveniente portare l'oggetto C

Si generano così altri due sottoproblemi: portare l'oggetto C e l'oggetto A oppure portare l'oggetto C e non portare l'oggetto A.

Nodo3 (figlio nodo 1)

x₁=1; x₂=1

z =32x₃+12x₄+69

18x₃+7x₄<=-5          non ha soluzioni

Nodo4(figlio nodo 1)

x₁=1;  x₂=0

z=26+32x₃+12x₄

18x₃+7x₄<=17                 

; arrotondando CBUB = 56

Siccome è più conveniente non portare l'oggetto C, si generano due sottoproblemi corrispondenti a non portare l'oggetto C e portare l'oggetto A oppure  a non portare i due oggetti  C e A.

Nodo5(figlio nodo 2)

x₁=0   x₂=1

z= 32x₃+12x₄+43

18x₃+7x₄<= 8       

CBUB (01) arrotondando CBUB (01) = 57

Nodo6(figlio nodo 2)

     x₁ = 0    x₂ = 0

z = 32x₃ + 12x₄

18x₃ + 7x₄ <= 30    CBUB(00) = 32 + 12 = 44

Essendo più conveniente non portare l'oggetto C e portare l'oggetto A, si generano due sotto problemi corrispondenti a non portare l'oggetto C e portare gli oggetti A e B oppure non portare gli oggetti C e B e portare l'oggetto A.

Nodo7(figlio nodo 5)

    x₁ = 0    x₂ = 1    x₃ = 1

z = 12x₄ + 75

7x₄ <= -10    non ha soluzioni ;

Nodo8(figlio nodo 5)

   x₁ = 0    x₂ = 1    x₃ = 1

z = 12x₄ + 43

7x₄ <= 8 ;   CBUB (010) = 43 + 12 = 55

Essendo più conveniente portare l'oggetto C e non portare l'oggetto A si generano due sotto problemi corrispondenti a portare gli oggetti C e B e non portare l'oggetto A oppure portare l'oggetto C e non portare gli oggetti A e B.

Nodo9(figlio nodo 4)

    x₁ = 1    x₂ = 0    x₃ = 1

z = 12x₄ + 58

7x₄ <= -1    non ha soluzioni;

Nodo10(figlio nodo 4)

   x₁ = 1    x₂ = 0    x₃ = 0

z = 12x₄ + 26

7x₄ <= 17  ;  CBUB(100)= 26 + 12 = 38

Soluzione ottimale è quella di portare gli oggetti A e D con valore complessivo 55 e peso 29 ossia la soluzione  corrispondente a (010) avendo il valore migliore tra quelli correnti.                                              

Albero decisionale

Il problema dello zaino può essere risolto mediante il metodo branch and bound  riempendo i campi dell'Applet seguente , cliccando sul tasto Inizia e poi sul tasto Risolvi,apparirà l'albero decisionale e la soluzione ottimale del problema.

  IL problema knapsack trova applicazione nei progetti di investimento finanziario.