/ / Rygsæk Problem i Excel VBA

Rygsæk Problem i Excel VBA

Nedenfor vil vi se på et program i Excel VBA at løser en lille forekomst af a knapsack problem.

Definition: I betragtning af et sæt elementer, hver med en vægt og en værdi, bestemmer de elementer, der skal inkluderes 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 hidrører fra det problem, der står over for en person, der er begrænset af en ryggsække i fast størrelse og skal udfylde det med de mest nyttige ting.

Eksempel: 5 elementer med vægt, værdier og grænse som angivet.

Rygsække problembillede

I Excel ser dette problem ud som følger:

Rygsæk Problem Eksempel

1. Først erklærer vi fem variabler af typen Double med navne grænse, vægt, værdi, totalVægt og maksimumValue.

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

2. Herefter erklærer vi fem variabler af typen Integer med med navne i, j, k, l, m.

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

3. Vi initialiserer to variabler. Vi initialiserer variabelgrænsen med værdien af ​​celle D6. Vi initialiserer den variable maksimumValue med værdi 0.

limit = Range("D6").value
maximumValue = 0

4. Næste kontrollerer vi enhver mulig løsning. Vi kan enten inkludere et emne (1) eller lade det være (0). Vi starter 5 til næste løkker. Én for hver vare.

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

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

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

6. Kun hvis værdien er højere end maksimumValue og vægt er lavere end grænse, har vi fundet en ny bedre løsning.

If value > maximumValue And weight <= limit Then

7. Hvis sandt, skriver vi den nye løsning til række 4, vægt til totalvægt og værdi til maksimumValue.

Range("B4").value = i
Range("C4").value = j
Range("D4").value = k
Range("E4").value = l
Range("F4").value = m
totalWeight = weight
maximumValue = value

8. Glem ikke at lukke If-erklæringen.

End If

9. Husk at lukke 5 For Next-løkkerne.

                Next m
            Next l
        Next k
    Next j
Next i

Excel VBA kontrollerer hver mulig løsning på denne måde, og som følge heraf vil den optimale løsning vises i række 4. Husk, at 1 betyder, at vi inkluderer et element, 0 betyder, at vi forlader det.

10. Til sidst skal du skrive totalVægt og maksimumValue for den optimale løsning til henholdsvis celle B6 og B8.

Range("B6").value = totalWeight
Range("B8").value = maximumValue

11. Test programmet.

Resultat:

Rygsæk Problem Resultat

Konklusion: Det er optimalt at inkludere de sidste fire emner med en maksimal værdi på 15. Denne løsning med en samlet vægt på 2 + 1 + 1 + 4 = 8 overstiger ikke grænsen på 15.

Bemærk: Ved at lave vægten og værdierne kan du løse eventuelle problemer med rygsæk af denne størrelse (se downloadbar Excel-fil).

Læs også: