Das Knapsack-problem
ich fand das Knapsack problem, schwierig und interessant zugleich. Ich bin sicher, wenn Sie diese Seite besuchen, kennen Sie die Problemanweisung bereits, aber nur zum Zwecke der Vervollständigung :
Problem:
Bei einem Rucksack mit einer maximalen Kapazität von W und N Elementen mit jeweils eigenem Wert und Gewicht werfen Sie Elemente in den Rucksack, so dass der endgültige Inhalt den Maximalwert hat. Huch !!,
Hier ist die allgemeine Art und Weise, wie das Problem erklärt wird – Wenn ein Dieb in ein Haus kommt, um auszurauben, und er trägt einen Rucksack. Es gibt eine feste Anzahl von Gegenständen im Haushalt – jedes mit seinem eigenen Gewicht und Wert-Schmuck, mit weniger Gewicht und höchstem Wert im Vergleich zu Tabellen, mit weniger Wert, aber viel schwer. Um dem Feuer Treibstoff hinzuzufügen, hat der Dieb einen alten Rucksack mit begrenzter Kapazität. Offensichtlich kann er den Tisch nicht in zwei Hälften oder drei Viertel aufteilen., Er nimmt es entweder oder lässt es stehen
Beispiel:
Knapsack Max weight : W = 10 (units)Total items : N = 4Values of items : v = {10, 40, 30, 50}Weight of items : w = {5, 4, 6, 3}
Ein flüchtiger Blick auf die Beispieldaten sagt uns, dass der maximale Wert, den wir mit dem Limit des maximalen Gewichts von 10 aufnehmen könnten, 50 + 40 = 90 mit einem Gewicht von 7 ist.
Ansatz:
Dies wird optimal gelöst, indem dynamische Programmierlösungen für kleinere Rucksackprobleme verwendet und diese dann für das größere Problem erweitert werden.,
Erstellen wir ein Item x Weight Array mit dem Namen V (Value array):
V = 4 rows * 10 columnsJeder der Werte in dieser Matrix stellt ein kleineres Rucksackproblem dar.
Basisfall 1: Nehmen wir den Fall der 0. Spalte. Es bedeutet nur, dass der Rucksack 0 Kapazität hat. Was kannst du in ihnen halten? Nichts. Füllen wir sie also alle mit 0s.
Basisfall 2: Nehmen wir den Fall der 0-Zeile. Es bedeutet nur, dass es keine Gegenstände im Haus gibt. Was halten Sie in Ihrem Rucksack, wenn es keine Gegenstände gibt? Wieder nichts !!! Alle Nullen.,
Lösung:
1) Beginnen wir nun, das Array zeilenweise auszufüllen. Was bedeuten Zeile 1 und Spalte 1? Dass das erste Element gegeben (Zeile), können Sie es in den Rucksack mit der Kapazität aufnehmen 1 (Spalte). Nein. Das Gewicht des ersten Artikels beträgt 5. Also, lass uns 0 ausfüllen. Tatsächlich könnten wir nichts ausfüllen, bis wir die Spalte 5 (Gewicht 5) erreicht haben.
2) Sobald wir Spalte 5 (die Gewicht 5 darstellt) in der ersten Zeile erreicht haben, bedeutet dies, dass wir Artikel 1 aufnehmen können., Lassen Sie uns dort 10 ausfüllen (denken Sie daran, dies ist ein Wert – Array):
3) Weitermachen, für Gewicht 6 (Spalte 6), können wir alles andere mit dem verbleibenden Gewicht von 1 aufnehmen (Gewicht – Gewicht dieses Artikels => 6-5). Hey, denk dran, wir sind auf dem ersten Punkt. Es ist also irgendwie intuitiv, dass der Rest der Zeile auch nur den gleichen Wert hat, da wir für das zusätzliche Gewicht, das wir haben, keinen anderen Artikel hinzufügen können.,
4) Das nächste Interessante passiert also, wenn wir die Spalte 4 in der dritten Zeile erreichen. Das aktuelle Laufgewicht beträgt 4.
Wir sollten für die folgenden Fälle überprüfen.
1) Können wir Artikel 2 aufnehmen-Ja, wir können. Artikel 2 Gewicht ist 4.
2) Ist der Wert für das aktuelle Gewicht ohne Punkt 2 höher? – Überprüfen Sie die vorherige Zeile auf das gleiche Gewicht. Nein. die vorherige Zeile* hat 0, da wir Artikel 1 in Gewicht 4 nicht aufnehmen konnten.
3) Können wir zwei Elemente im gleichen Gewicht unterbringen, damit wir den Wert maximieren können? – Nein., Das verbleibende Gewicht nach Abzug des Gewichts des Item2 ist 0.
Warum vorherigen Zeile?
Einfach, weil die vorherige Zeile bei Gewicht 4 selbst eine kleinere Rucksacklösung ist, die den Maximalwert angibt, der bis zu diesem Punkt für dieses Gewicht akkumuliert werden könnte (Durchlaufen der Elemente).,
Beispielhaft,
1) Der Wert des aktuellen Artikels = 40
2) Das Gewicht des aktuellen Artikels = 4
3) Das verbleibende Gewicht = 4 – 4 = 0
4) Überprüfen Sie die obige Zeile (der obige Artikel bei Artikel 1 oder der kumulative Maximalwert bei den restlichen Zeilen). Sind wir für das verbleibende Gewicht 0 in der Lage, Artikel 1 aufzunehmen? Einfach ausgedrückt, gibt es in der obigen Zeile überhaupt einen Wert für das angegebene Gewicht?,
Die Berechnung geht so:
1) Nehmen Sie den Maximalwert für dasselbe Gewicht ohne diesen Artikel:
previous row, same weight = 0=> V2) Nehmen Sie den Wert des aktuellen Artikels + Wertes, den wir mit dem verbleibenden Gewicht aufnehmen könnten:
Max unter den beiden ist 40 (0 und 40).
3) Das nächste und wichtigste Ereignis findet in Spalte 9 und Zeile 2 statt. Das heißt, wir haben ein Gewicht von 9 und wir haben zwei Artikel. Wenn wir uns die Beispieldaten ansehen, könnten wir die ersten beiden Elemente aufnehmen., Hier betrachten wir einige Dinge:
- Der Wert des aktuellen Elements = 40
- Das Gewicht des aktuellen Elements = 4
- Das verbleibende Gewicht = 9 – 4 = 5
- Überprüfen Sie die obige Zeile. Bei dem verbleibenden Gewicht 5, sind wir in der Lage, Artikel unterzubringen 1.
Die Berechnung lautet also :
1) Nehmen Sie den Maximalwert für dasselbe Gewicht ohne diesen Artikel:
previous row, same weight = 102) Nehmen Sie den Wert des aktuellen Artikels + Wertes, den wir mit dem verbleibenden Gewicht akkumulieren könnten:
Value of current item (40)+ value in previous row with weight 5 (total weight until now (9) - weight of the current item (4))= 1010 vs 50 = 50.,
Am Ende der Lösung all dieser kleineren Probleme müssen wir nur den Wert bei V-Item 4 bei Weight 10:
Complexity
Die Analyse der Komplexität der Lösung ist ziemlich einfach. Wir haben nur eine Schleife für W innerhalb einer Schleife von N = O (NW)
Implementierung:
Hier kommt der obligatorische Implementierungscode in Java: