Nedenfor ser vi på et program i Excel VBA at løser en liten forekomst av a ryggsekk problem.
Definisjon: Gitt et sett med varer, hver med en vekt og en verdi, bestemme elementene som skal inkluderes i en samling, slik at den totale verdien er så stor som mulig og den totale vekten er mindre enn en gitt grense. Det henter navnet sitt fra problemet som står overfor noen som er begrenset av en ryggsekk med fast størrelse og må fylle den med de mest nyttige elementene.
Eksempel: 5 elementer med vekter, verdier og grenser som angitt.
I Excel ser dette problemet slik ut:
1. For det første erklærer vi fem variabler av typen Double med navnegrense, vekt, verdi, totalvekt og maksimalverdi.
Dimgrense As Double, weight As Double, value As Double, totalWeight As Double, maximumValue As Double
2. Deretter deklarerer vi fem variabler av typen Heltall med navnene i, j, k, l, m.
Dim i, j, k, l, m As Integer
3. Vi initialiserer to variabler. Vi initialiserer variabelgrensen med verdien av celle D6. Vi initialiserer variabelen maximumValue med verdi 0.
limit = Range ("D6"). verdi
maksimalverdi = 0
4. Deretter sjekker vi hver mulig løsning. Vi kan enten inkludere et element (1) eller la det være ute (0). Vi starter 5 For Next loops. En for hvert element.
For i = 0 til 1
For j = 0 til 1
For k = 0 til 1
For l = 0 til 1
For m = 0 til 1
5. Vi beregner vekten og verdien av en mulig løsning.
vekt = 12 * i + 2 * j + 1 * k + 1 * l + 4 * m
verdi = 4 * i + 2 * j + 2 * k + 1 * l + 10 * m
6. Bare hvis verdien er høyere enn maksimalverdi og vekten er lavere enn grensen, har vi funnet en ny bedre løsning.
Hvis verdi> maksimalverdi og vekt <= grense Da
7. Hvis det er sant, skriver vi den nye løsningen til rad 4, vekt til totalvekt og verdi til maksimalverdi.
Område ("B4"). Verdi = i
Område ("C4"). Verdi = j
Område ("D4"). Verdi = k
Område ("E4"). Verdi = l
Område ("F4"). Verdi = m
totalvekt = vekt
maksimalverdi = verdi
8. Ikke glem å lukke If -setningen.
Slutt om
9. Ikke glem å lukke 5 For Next -løkkene.
Neste m
Neste l
Neste k
Neste j
Neste jeg
Excel VBA sjekker hver mulig løsning på denne måten, og som et resultat vil den optimale løsningen vises i rad 4. Husk, 1 betyr at vi inkluderer et element, 0 betyr at vi utelater det.
10. Skriv til slutt totalvekt og maksimalverdi for den optimale løsningen til henholdsvis celle B6 og B8.
Område ("B6"). Verdi = totalvekt
Område ("B8"). Verdi = maksimalverdi
11. Test programmet.
Resultat:
Konklusjon: det er optimalt å inkludere de fire siste elementene med en maksimal verdi på 15. Denne løsningen med en totalvekt på 2 + 1 + 1 + 4 = 8 overskrider ikke grensen på 15.
Merk: Ved å gjøre vektene og verdiene variable kan du løse ethvert ryggsekkproblem av denne størrelsen (se nedlastbar Excel -fil).
