Di seguito vedremo un programma in Excel VBA Quello risolve una piccola istanza di a problema con lo zaino.
Definizione: dato un insieme di articoli, ciascuno con un peso e un valore, determinare gli articoli da includere in una collezione in modo che il valore totale sia il più grande possibile e il peso totale sia inferiore a un determinato limite. Deriva il suo nome dal problema affrontato da chi è vincolato da uno zaino di dimensioni fisse e deve riempirlo con gli oggetti più utili.
Esempio: 5 articoli con pesi, valori e limite come indicato.
In Excel questo problema si presenta come segue:
1. Innanzitutto, dichiariamo cinque variabili di tipo Double con i nomi limit, weight, value, totalWeight e maximumValue.
Dim limit As Double, peso As Double, valore As Double, totalWeight As Double, valore massimo As Double
2. Successivamente, dichiariamo cinque variabili di tipo Integer con nomi i, j, k, l, m.
Dim i, j, k, l, m As Integer
3. Inizializziamo due variabili. Inizializziamo la variabile limit con il valore della cella D6. Inizializziamo la variabile maximumValue con valore 0.
limite = Intervallo("D6").valore
valoremassimo = 0
4. Successivamente, controlliamo ogni possibile soluzione. Possiamo includere un elemento (1) o tralasciarlo (0). Iniziamo 5 For Next loop. Uno per ogni articolo.
Per i = da 0 a 1
Per j = da 0 a 1
Per k = da 0 a 1
Per l = da 0 a 1
Per m = da 0 a 1
5. Calcoliamo il peso e il valore di una possibile soluzione.
peso = 12 * i + 2 * j + 1 * k + 1 * l + 4 * m
valore = 4 * i + 2 * j + 2 * k + 1 * l + 10 * m
6. Solo se il valore è superiore al valore massimo e il peso è inferiore al limite, abbiamo trovato una nuova soluzione migliore.
Se valore > valore massimo E peso <= limite Allora
7. Se vero, scriviamo la nuova soluzione nella riga 4, peso su totalWeight e valore su maximumValue.
Intervallo("B4").valore = i
Intervallo("C4").valore = j
Intervallo ("D4"). valore = k
Intervallo("E4").valore = l
Intervallo ("F4"). valore = m
Peso totale = peso
valoremassimo = valore
8. Non dimenticare di chiudere l'istruzione If.
Finisci se
9. Non dimenticare di chiudere i cicli 5 For Next.
prossimo m
Avanti
Successivo k
Avanti j
Avanti io
Excel VBA controlla ogni possibile soluzione in questo modo e, di conseguenza, la soluzione ottimale apparirà nella riga 4. Ricorda, 1 significa che includiamo un elemento, 0 significa che lo tralasciamo.
10. Infine, scrivi totalWeight e maximumValue della soluzione ottima rispettivamente nella cella B6 e B8.
Intervallo ("B6"). valore = peso totale
Intervallo("B8").valore = valoremassimo
11. Testare il programma.
Risultato:
Conclusione: è ottimale 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: rendendo variabili pesi e valori si risolve qualsiasi problema di zaino di queste dimensioni (vedi file Excel scaricabile).
