Di seguito vedremo un programma in Excel VBA che risolve un piccolo esempio di un problema di zaino.

Definizione: Dato un insieme di elementi, ciascuno con un peso e un valore, determinare gli elementi da includere in un insieme in modo che il valore totale è il più ampio possibile e il peso totale è inferiore ad un determinato limite.

Il suo nome deriva dal problema affrontato da qualcuno che è vincolata da uno zaino di dimensioni fisse e deve riempire con i prodotti più utili.

Esempio: 5 oggetti con pesi, valori limite e trovati.

Knapsack Problem Image

In Excel questo problema si presenta come segue:

Knapsack Problem Example

  1. In primo luogo, si dichiara cinque variabili di tipo matrimoniale con limite di nomi, il peso, il valore, e pesoTotale MaximumValue.

Dim limit As Double, weight As Double, value As Double, totalWeight As Double, maximumValue As Double

  1. Successivamente, si dichiara cinque variabili di tipo intero con nomi i, j, k, l, m.

Dim i, j, k, l, m As Integer

  1. si inizializza due variabili. Inizializziamo il limite variabile con il valore della cella D6. Inizializziamo la MaximumValue variabile con valore 0.

limit = Range("D6").value

maximumValue = 0

  1. Successivamente, controllare ogni possibile soluzione. o possiamo includere un elemento (1) o lasciarlo fuori (0). Iniziamo 5 Per i cicli successivi. Uno per ogni voce.

For i = 0 To 1

For j = 0 To 1

For k = 0 To 1

For l = 0 To 1

For m = 0 To 1

  1. Si calcola il peso e il valore di una possibile soluzione.

weight = 12  i + 2  j + 1  k + 1  l + 4  m

value = 4  i + 2  j + 2  k + 1  l + 10  m

  1. Solo se il valore è superiore a MaximumValue e il peso è inferiore al limite, abbiamo trovato una nuova soluzione migliore.

If value > maximumValue And weight <= limit Then

  1. Se è vero, si scrive la nuova soluzione per fila 4, peso e pesoTotale valore MaximumValue.

Range("B4").value = i

Range("C4").value = j

Range("D4").value = k

Range("E4").value = l

Range("F4").value = m

totalWeight = weight

maximumValue = value

  1. Non dimenticare di chiudere l’istruzione if.

End If

  1. Non dimenticare di chiudere il 5 per cicli successivi.

Next m

Next l

Next k

Next j

Next i

Excel VBA controlla ogni soluzione possibile in questo modo e di conseguenza apparirà la soluzione ottimale in fila 4. Si ricordi, 1 mezzi includiamo un elemento, 0 significa lasciamo fuori.

  1. Infine, scrivere pesoTotale e MaximumValue della soluzione ottima rispettivamente cella B6 e B8.

Range("B6").value = totalWeight

Range("B8").value = maximumValue

  1. Test del programma.

Risultato:

Knapsack Problem Result

Conclusione: è ottimale per includere gli ultimi quattro elementi con un valore massimo di 15. Questa soluzione con un peso totale di 2 + 1 + 1 + 4 = 8 non supera il limite di 15.

Nota: facendo la variabile pesi e valori che è possibile risolvere qualsiasi problema dello zaino di queste dimensioni (vedi file Excel scaricabile).