Nedan kommer vi att titta på ett program i Excel VBA det där löser en liten förekomst av a ryggsäck problem.
Definition: Med tanke på en uppsättning artiklar, var och en med en vikt och ett värde, bestäm de 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 given gräns. Det härleder sitt namn från problemet med någon som är begränsad av en ryggsäck med fast storlek och måste fylla den med de mest användbara föremålen.
Exempel: 5 artiklar med vikter, värden och gräns som anges.
I Excel ser problemet ut så här:
1. Först deklarerar vi fem variabler av typ Double med namngräns, vikt, värde, totalvikt och maximumValue.
Dimgräns As Double, vikt As Double, value As Double, totalWeight As Double, maximumValue As Double
2. Därefter deklarerar vi fem variabler av typen Heltal med namnen i, j, k, l, m.
Dim i, j, k, l, m Som heltal
3. Vi initierar två variabler. Vi initierar variabelgränsen med värdet på cell D6. Vi initierar variabeln maximumValue med värde 0.
limit = Range ("D6"). värde
maximumValue = 0
4. Därefter kontrollerar vi varje möjlig lösning. Vi kan antingen inkludera ett objekt (1) eller utelämna det (0). Vi startar 5 för nästa slingor. En för varje vara.
För i = 0 till 1
För j = 0 till 1
För k = 0 till 1
För l = 0 till 1
För m = 0 till 1
5. Vi beräknar vikten och värdet av en möjlig lösning.
vikt = 12 * i + 2 * j + 1 * k + 1 * l + 4 * m
värde = 4 * i + 2 * j + 2 * k + 1 * l + 10 * m
6. Endast om värdet är högre än maxvärdet och vikten är lägre än gränsen har vi hittat en ny bättre lösning.
Om värde> maximumValue And weight <= limit Then
7. Om det stämmer skriver vi den nya lösningen till rad 4, vikt till totalvikt och värde till maximumValue.
Område ("B4"). Värde = i
Område ("C4"). Värde = j
Område ("D4"). Värde = k
Område ("E4"). Värde = l
Område ("F4"). Värde = m
totalvikt = vikt
maximumValue = värde
8. Glöm inte att stänga if -uttalandet.
Avsluta om
9. Glöm inte att stänga 5 For Next -slingorna.
Nästa m
Nästa l
Nästa k
Nästa j
Nästa 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 utelämnar det.
10. Skriv slutligen totalWeight och maximumValue av den optimala lösningen till cell B6 respektive B8.
Område ("B6"). Value = totalWeight
Område ("B8"). Värde = maximumValue
11. Testa programmet.
Resultat:
Slutsats: det är optimalt att inkludera de fyra sista objekten med ett maximivärde på 15. Denna lösning med en totalvikt på 2 + 1 + 1 + 4 = 8 överskrider inte gränsen på 15.
Obs: genom att göra vikter och värden variabel kan du lösa alla ryggsäckproblem av denna storlek (se nedladdningsbar Excel -fil).
