Nedenfor ser vi på et program i Excel VBA at løser en lille forekomst af a rygsæk problem.
Definition: I betragtning af et sæt varer, der hver har en vægt og en værdi, skal du bestemme de elementer, der skal medtages i en samling, så den samlede værdi er så stor som muligt, og den samlede vægt er mindre end en given grænse. Det stammer sit navn fra problemet med en person, der er begrænset af en rygsæk med fast størrelse og skal fylde det med de mest nyttige ting.
Eksempel: 5 varer med vægte, værdier og grænse som angivet.
I Excel ser dette problem sådan ud:
1. For det første erklærer vi fem variabler af typen Double med navnegrænse, vægt, værdi, totalVægt og maksimalværdi.
Dimgrænse som dobbelt, vægt som dobbelt, værdi som dobbelt, totalVægt som dobbelt, maksimal værdi som dobbelt
2. Dernæst erklærer vi fem variabler af typen Heltal med navnene i, j, k, l, m.
Dim i, j, k, l, m Som heltal
3. Vi initialiserer to variabler. Vi initialiserer variabelgrænsen med værdien af celle D6. Vi initialiserer variablen maximumValue med værdi 0.
limit = Range ("D6"). værdi
maksimalværdi = 0
4. Dernæst kontrollerer vi hver mulig løsning. Vi kan enten inkludere et element (1) eller lade det være ude (0). Vi starter 5 til næste sløjfer. En for hver vare.
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 vægten og værdien af en mulig løsning.
vægt = 12 * i + 2 * j + 1 * k + 1 * l + 4 * m
værdi = 4 * i + 2 * j + 2 * k + 1 * l + 10 * m
6. Kun hvis værdien er højere end maksimumværdi og vægten er lavere end grænsen, har vi fundet en ny bedre løsning.
Hvis værdi> maks. Værdi og vægt <= grænse Så
7. Hvis det er sandt, skriver vi den nye løsning til række 4, vægt til totalVægt og værdi til maksimalværdi.
Område ("B4"). Værdi = i
Område ("C4"). Værdi = j
Område ("D4"). Værdi = k
Område ("E4"). Værdi = l
Område ("F4"). Værdi = m
totalvægt = vægt
maximumValue = værdi
8. Glem ikke at lukke If -sætningen.
Afslut Hvis
9. Glem ikke at lukke de 5 For Next -sløjfer.
Næste m
Næste l
Næste k
Næste j
Næste i
Excel VBA kontrollerer hver mulig løsning på denne måde, og som følge heraf vises den optimale løsning i række 4. Husk, 1 betyder, at vi inkluderer et element, 0 betyder, at vi udelader det.
10. Skriv endelig TotalWeight og maximumValue af den optimale løsning til henholdsvis celle B6 og B8.
Område ("B6"). Værdi = totalVægt
Område ("B8"). Værdi = maksimalværdi
11. Test programmet.
Resultat:
Konklusion: det er optimalt at inkludere de sidste fire emner med en maksimal værdi på 15. Denne løsning med en totalvægt på 2 + 1 + 1 + 4 = 8 overstiger ikke grænsen på 15.
Bemærk: Ved at gøre vægte og værdier variable kan du løse ethvert rygsækproblem af denne størrelse (se Excel -fil, der kan downloades).
