/ / Knackack Problem in Excel VBA

Knapsack Problem in Excel VBA

Unten sehen wir uns ein Programm in Excel VBA Das löst eine kleine Instanz von a Rucksackproblem.

Definition: Bei einer Menge von Elementen, die jeweils ein Gewicht und einen Wert haben, bestimmen Sie die Elemente, die in eine Sammlung aufgenommen werden sollen, so dass der Gesamtwert so groß wie möglich ist und das Gesamtgewicht weniger als ein vorgegebenes Limit ist. Es leitet seinen Namen von dem Problem ab, dem jemand gegenübersteht, der durch einen Rucksack fester Größe eingeschränkt ist, und muss ihn mit den nützlichsten Gegenständen füllen.

Beispiel: 5 Elemente mit Gewichten, Werten und Limit wie angegeben.

Rucksack-Image

In Excel sieht dieses Problem folgendermaßen aus:

Knapsack Problem Beispiel

1. Zuerst deklarieren wir fünf Variablen vom Typ Double mit Namen limit, weight, value, totalWeight und maximumValue.

Dim limit As Double, weight As Double, value 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 von Zelle D6. Wir initialisieren die Variable maximumValue mit dem Wert 0.

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

4. Als nächstes prüfen wir jede mögliche Lösung. Wir können entweder einen Gegenstand (1) hinzufügen oder ihn weglassen (0). Wir starten 5 For Next Loops. Eins für jeden Gegenstand.

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. Wir berechnen das Gewicht und den Wert einer möglichen Lösung.

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

6. Nur wenn der Wert höher als der Maximalwert ist und das Gewicht niedriger als der Grenzwert ist, haben wir eine neue bessere Lösung gefunden.

If value > maximumValue And weight <= limit Then

7. Wenn dies zutrifft, schreiben wir die neue Lösung in Zeile 4, Gewicht in TotalWeight und Wert in 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. Vergessen Sie nicht, die If-Anweisung zu schließen.

End If

9. Vergessen Sie nicht, die 5 For Next-Loops zu schließen.

                Next m
            Next l
        Next k
    Next j
Next i

Excel VBA überprüft jede mögliche Lösung auf diese Weise, und als Ergebnis wird die optimale Lösung in Zeile 4 angezeigt. Denken Sie daran, dass 1 bedeutet, dass wir ein Element einschließen, 0 bedeutet, dass wir es auslassen.

10. Schließlich schreibe TotalWeight und MaximumValue der optimalen Lösung für die Zellen B6 bzw. B8.

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

11. Testen Sie das Programm.

Ergebnis:

Knapsack Problem Ergebnis

Schlussfolgerung: Es ist optimal, die letzten vier Punkte mit einem maximalen Wert von 15 einzubeziehen. 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).

Lesen Sie auch: