Ryggsäcksproblem i Excel VBA

Nedan ser vi på ett program i Excel VBA den där löser en liten instans av a ryggsäck problem.

Definition: Med en uppsättning artiklar, var och en med en vikt och ett värde, bestämmer du vilka objekt som ska inkluderas i en samling så att det totala värdet är så stort som möjligt och den totala vikten är mindre än en viss gräns. Det härletar sitt namn från problemet inför någon som är begränsad av en ryggsäck i fast storlek och måste fylla den med de mest användbara föremålen.

Exempel: 5 objekt med vikter, värden och gräns som anges.

I Excel ser detta problem ut som följer:

1. Först deklarerar vi fem variabler av typen Double med namngränsen, vikt, värde, totalvikt och maximumValue.

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

2. Vi förklarar därefter fem variabler av typen Integer med med namn i, j, k, l, m.

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

3. Vi initierar två variabler. Vi initierar variabelgränsen med värdet av cell D6. Vi initierar den variabla maximumValue med värde 0.

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

4. Nästa, vi kontrollerar varje möjlig lösning. Vi kan antingen inkludera ett objekt (1) eller lämna det ut (0). Vi startar 5 för nästa loopar. En för varje objekt.

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 beräknar vikten och värdet av en möjlig 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. Endast om värdet är högre än maximumValue och vikt är lägre än gräns, vi har hittat en ny bättre lösning.

If value > maximumValue And weight <= limit Then

7. Om sant, skriver vi den nya lösningen till rad 4, vikt till totalvikt och värde till maximumValue.

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. Glöm inte att stänga If-förklaringen.

End If

9. Glöm inte att stänga 5 till nästa loopar.

                Next m
            Next l
        Next k
    Next j
Next i

Excel VBA kontrollerar varje möjlig lösning på detta sätt och som ett resultat kommer den optimala lösningen att visas i rad 4. Kom ihåg att 1 betyder att vi inkluderar ett objekt, 0 betyder att vi lämnar den ut.

10. Slutligen, skriv totalVikt och maximumValue av den optimala lösningen till respektive cell B6 och B8.

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

11. Testa programmet.

Resultat:

Slutsats: Det är optimalt att inkludera de fyra sista objekten med ett maximumvärde på 15. Denna lösning med en totalvikt på 2 + 1 + 1 + 4 = 8 överstiger inte gränsen på 15.

Obs! Genom att göra vikten och värdena kan du lösa eventuella ryggsäckproblem av den här storleken (se nedladdningsbar Excel-fil).