Implementierung des Rucksackproblems in Java

1. Einleitung

Das Rucksackproblem ist ein kombinatorisches Optimierungsproblem, das viele Anwendungen hat. In diesem Tutorial lösen wir dieses Problem in Java.

2. Das Rucksackproblem

Im Rucksackproblem haben wir eine Reihe von Gegenständen. Jeder Artikel hat ein Gewicht und einen Wert:

Wir wollen diese Gegenstände in einen Rucksack stecken. Es gibt jedoch eine Gewichtsbeschränkung:

Daher müssen wir die Artikel auswählen, deren Gesamtgewicht die Gewichtsgrenze nicht überschreitet und deren Gesamtwert so hoch wie möglich ist. Die beste Lösung für das obige Beispiel ist beispielsweise die Auswahl des 5-kg-Artikels und des 6-kg-Artikels, was einen Maximalwert von 40 USD innerhalb der Gewichtsgrenze ergibt.

Das Rucksackproblem weist mehrere Variationen auf. In diesem Tutorial konzentrieren wir uns auf das 0-1-Rucksackproblem. Beim 0-1-Rucksackproblem muss jeder Gegenstand entweder ausgewählt oder zurückgelassen werden. Wir können keinen Teilbetrag eines Artikels nehmen. Wir können einen Artikel auch nicht mehrmals nehmen.

3. Mathematische Definition

Lassen Sie uns nun das 0-1-Rucksackproblem in mathematischer Notation formalisieren. Bei einer Menge von n Elementen und der Gewichtsgrenze W können wir das Optimierungsproblem wie folgt definieren:

Dieses Problem ist NP-schwer. Daher gibt es derzeit keinen Polynom-Zeit-Algorithmus, um dies zu lösen. Es gibt jedoch einen Pseudo-Polynom-Zeitalgorithmus, der dynamische Programmierung für dieses Problem verwendet.

4. Rekursive Lösung

Wir können eine Rekursionsformel verwenden, um dieses Problem zu lösen:

In dieser Formel ist M (n, w) die optimale Lösung für n Gegenstände mit einer Gewichtsgrenze w . Dies ist das Maximum der folgenden zwei Werte:

  • Die optimale Lösung aus (n-1) Artikeln mit der Gewichtsgrenze w (ohne den n- ten Artikel)
  • Wert des n- ten Elements plus der optimalen Lösung aus (n-1) Elementen und w minus Gewicht des n- ten Elements (einschließlich des n- ten Elements)

Wenn das Gewicht des n- ten Elements größer als das aktuelle Gewichtslimit ist, wird es nicht berücksichtigt. Daher gehört es zur ersten Kategorie der beiden oben genannten Fälle.

Wir können diese Rekursionsformel in Java implementieren:

int knapsackRec(int[] w, int[] v, int n, int W) { if (n  W) { return knapsackRec(w, v, n - 1, W); } else { return Math.max(knapsackRec(w, v, n - 1, W), v[n - 1] + knapsackRec(w, v, n - 1, W - w[n - 1])); } } 

In jedem Rekursionsschritt müssen zwei suboptimale Lösungen bewertet werden. Daher beträgt die Laufzeit dieser rekursiven Lösung O (2n).

5. Dynamische Programmierlösung

Dynamische Programmierung ist eine Strategie zur Linearisierung ansonsten exponentiell schwieriger Programmierprobleme. Die Idee ist, die Ergebnisse von Teilproblemen zu speichern, damit wir sie später nicht neu berechnen müssen.

Wir können das 0-1-Rucksackproblem auch mit dynamischer Programmierung lösen. Zur Nutzung der dynamische Programmierung, wir zuerst eine 2-dimensionale Tabelle mit Abmessungen von 0 bis schaffen n und 0 bis W . Dann verwenden wir einen Bottom-up-Ansatz, um die optimale Lösung mit dieser Tabelle zu berechnen:

int knapsackDP(int[] w, int[] v, int n, int W) { if (n <= 0 || W <= 0) { return 0; } int[][] m = new int[n + 1][W + 1]; for (int j = 0; j <= W; j++) { m[0][j] = 0; } for (int i = 1; i <= n; i++) { for (int j = 1; j  j) { m[i][j] = m[i - 1][j]; } else { m[i][j] = Math.max( m[i - 1][j], m[i - 1][j - w[i - 1]] + v[i - 1]); } } } return m[n][W]; } 

Bei dieser Lösung haben wir eine verschachtelte Schleife über die Artikelnummer , n und die Gewichtsgrenze W . Daher ist die Laufzeit O (nW) .

6. Fazit

In diesem Tutorial haben wir eine mathematische Definition des 0-1-Rucksackproblems gezeigt. Dann haben wir eine rekursive Lösung für dieses Problem mit der Java-Implementierung bereitgestellt. Schließlich haben wir dynamische Programmierung verwendet, um dieses Problem zu lösen.

Wie immer ist der Quellcode für den Artikel auf GitHub verfügbar.