Im Folgenden werden wir ein Programm in Excel VBA suchen, die eine kleine Instanz eines Ranzen Problem löst.

Definition: eine Gruppe von Elementen gegeben, die jeweils mit einem Gewicht und einem Wert, bestimmen Sie die Elemente in einer Sammlung enthalten, so dass der Gesamtwert so groß wie möglich ist, und das Gesamtgewicht ist kleiner als ein vorgegebener Grenzwert.

Es leitet seinen Namen von dem Problem von jemandem gegenüber, die durch eine feste Größe Ranzen beschränkt ist und es mit den nützlichsten Gegenstände füllen müssen.

Beispiel: 5 Elemente mit Gewichten, Werte und Begrenzung als gegeben.

Knapsack Problem Image

In Excel sieht das Problem wie folgt:

Knapsack Problem Example

  1. Zuerst erklären wir fünf Variablen vom Typ Double mit Namen Grenze, Gewicht, Wert, Gesamtgewicht und Maximalwert.

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

  1. Als nächstes erklären wir fünf Variablen vom Typ Integer mit mit Namen i, j, k, l, m.

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

  1. Wir initialisieren zwei Variablen. Wir initialisieren die Variable Grenze mit dem Wert der Zelle D6. Wir initialisieren die Variable Maximumwert von 0

limit = Range("D6").value

maximumValue = 0

  1. Als nächstes überprüfen wir jede mögliche Lösung. Wir können entweder einen Punkt (1) umfassen oder es auslassen (0). Wir beginnen 5 für Next-Schleifen. Ein für jedes Element.

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

  1. 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

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

If value > maximumValue And weight <= limit Then

  1. Wenn das stimmt, schreiben wir die neue Lösung zur Reihe 4, um Gewicht zu Gesamtgewicht und den Wert Maximum.

Range("B4").value = i

Range("C4").value = j

Range("D4").value = k

Range("E4").value = l

Range("F4").value = m

totalWeight = weight

maximumValue = value

  1. Vergessen Sie nicht, die If-Anweisung zu schließen.

End If

  1. Vergessen Sie nicht, die 5 für Next-Schleifen zu schließen.

Next m

Next l

Next k

Next j

Next i

Excel VBA prüft jede mögliche Lösung auf diese Weise und als Ergebnis die optimale Lösung in der Reihe erscheint 4. Denken Sie daran, 1 bedeutet, dass wir ein Element umfassen, 0 bedeutet, dass wir es weglassen.

  1. Schließlich schreibt und Gesamtgewicht Maximum der optimalen Lösung, um jeweils die Zelle B6 und B8.

Range("B6").value = totalWeight

Range("B8").value = maximumValue

  1. Testen Sie das Programm.

Ergebnis:

Knapsack Problem Result

Fazit: Es ist optimal, um die letzten vier Elemente mit einem Maximalwert von 15. Diese Lösung mit einem Gesamtgewicht von 2 + 1 + 1 + 4 = 8 nicht überschreitet den Grenzwert von 15 zu schließen

Hinweis: durch die Gewichte und Werte variabel machen Sie jede Knapsackproblems dieser Größe lösen können (siehe Download-Excel-Datei).