Rygsækproblem

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ægt, værdier og grænse som angivet.

I Excel ser dette problem sådan ud:

oprettelse af en afskrivningsplan i Excel

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.

2. Dernæst erklærer vi fem variabler af typen Heltal med navnene i, j, k, l, m.

excel formel for dage mellem datoer

3. Vi initialiserer to variabler. Vi initialiserer variabelgrænsen med værdien af ​​celle D6. Vi initialiserer variablen maximumValue med væ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.

5. Vi beregner vægten og værdien af ​​en mulig løsning.

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.

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.

8. Glem ikke at lukke If -sætningen.

9. Glem ikke at lukke de 5 For Next -sløjfer.

konvertere streng til nummer i Excel

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 totalVægt og maksimalVærdi for den optimale løsning til henholdsvis celle B6 og B8.

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).