Im Folgenden sehen wir uns ein Programm in an Excel VBA das löst eine kleine Instanz von a Rucksackproblem.
Definition: Bestimmen Sie bei einer Reihe von Artikeln mit jeweils einem Gewicht und einem Wert die Artikel, die in eine Sammlung aufgenommen werden sollen, so dass der Gesamtwert so groß wie möglich ist und das Gesamtgewicht einen bestimmten Grenzwert unterschreitet. Es leitet seinen Namen von dem Problem ab, mit dem jemand konfrontiert ist, der durch einen Rucksack mit fester Größe eingeschränkt ist und ihn mit den nützlichsten Gegenständen füllen muss.
Beispiel: 5 Artikel mit Gewichten, Werten und Limit wie angegeben.
In Excel sieht dieses Problem wie folgt aus:
1. Zunächst deklarieren wir fünf Variablen vom Typ Double mit den Namen limit, weight, value, totalWeight und maximumValue.
Dim limit As Double, Gewicht As Double, Wert As Double, totalWeight As Double, maximumValue As Double
2. Als nächstes deklarieren wir fünf Variablen vom Typ Integer mit den Namen i, j, k, l, m.
Dim i, j, k, l, m As Integer
3. Wir initialisieren zwei Variablen. Wir initialisieren das Variablenlimit mit dem Wert der Zelle D6. Wir initialisieren die Variable maximumValue mit dem Wert 0.
limit = Range("D6").value
maximaler Wert = 0
4. Als nächstes prüfen wir jede mögliche Lösung. Wir können entweder ein Element hinzufügen (1) oder es weglassen (0). Wir starten 5 For Next-Schleifen. Eine für jeden Artikel.
Für i = 0 bis 1
Für j = 0 bis 1
Für k = 0 bis 1
Für l = 0 bis 1
Für m = 0 bis 1
5. Wir berechnen das Gewicht und den Wert einer möglichen Lösung.
Gewicht = 12 * i + 2 * j + 1 * k + 1 * l + 4 * m
Wert = 4 * i + 2 * j + 2 * k + 1 * l + 10 * m
6. Nur wenn value höher als maximumValue und weight niedriger als limit ist, haben wir eine neue bessere Lösung gefunden.
Wenn Wert > Maximalwert Und Gewicht <= Grenze Dann
7. Falls wahr, schreiben wir die neue Lösung in Zeile 4, weight in totalWeight und value in maximumValue.
Range("B4").value = i
Range("C4").value = j
Range("D4").value = k
Range("E4").value = l
Bereich("F4").Wert = m
Gesamtgewicht = Gewicht
maximumValue = Wert
8. Vergessen Sie nicht, die If-Anweisung zu schließen.
Ende Wenn
9. Vergessen Sie nicht, die 5 For Next-Schleifen zu schließen.
Nächstes m
Als nächstes l
Nächstes k
Nächstes j
Als nächstes
Excel VBA prüft jede mögliche Lösung auf diese Weise und als Ergebnis erscheint die optimale Lösung in Zeile 4. Denken Sie daran, 1 bedeutet, dass wir ein Element einfügen, 0 bedeutet, dass wir es weglassen.
10. Schreiben Sie schließlich totalWeight und maximumValue der optimalen Lösung in die Zelle B6 bzw. B8.
Range("B6").value = totalWeight
Range("B8").value = maximumValue
11. Testen Sie das Programm.
Ergebnis:
Fazit: Optimal sind die letzten vier Items mit einem Maximalwert von 15. Diese Lösung mit einem Gesamtgewicht von 2 + 1 + 1 + 4 = 8 überschreitet nicht die Grenze von 15.
Hinweis: Indem Sie die Gewichte und Werte variabel machen, können Sie jedes Rucksackproblem dieser Größe lösen (siehe herunterladbare Excel-Datei).
