Wie löst man einen Bruch-Rucksack in linearer Zeit? Ich habe dies bei Google gefunden, verstehe es aber nicht wirklich.
- Wählen Sie das Element $ r $ zufällig aus $ R $ (Satz von Gewinn / Gewichts-Verhältnissen)
- Bestimmen Sie
- $ R_1 = \ {p_i / w_i | p_i / w_i > r für 1 \ leq i \ leq n \}, W_1 = \ sum_ {i \ in R_1} w_i $
- $ R_2 = \ {p_i / w_i | p_i / w_i = r, für 1 \ leq i \ leq n \}, W_2 = \ sum_ {i \ in R_3} w_i $
- $ R_3 = \ {p_i / w_i | p_i / w_i < r, z 1 \ leq i \ leq n \}, W_3 = \ sum_ {i \ in R_3} w_i $
- wenn $ W_1 > W $
- rekursiere $ R_1 $ und gebe die berechnete Lösung zurück
- else
- while (in Rucksack und $ ist Platz R_2 $ ist nicht leer)
- Elemente aus $ R_2 $
- hinzufügen, wenn (Rucksack voll ist)
- Elemente in $ R_1 zurückgeben $ und Elemente, die gerade aus $ R_2 $
- hinzugefügt wurden, sonst
- reduzieren die Rucksackkapazität um $ W_1 + W_2 $
- auf $ R_3 $ und Artikel in $ R_1 \ cu zurückgeben p R_2 $
- Elemente hinzufügen, die von einem rekursiven Aufruf zurückgegeben wurden
- while (in Rucksack und $ ist Platz R_2 $ ist nicht leer)
Ich verstehe nicht, wie es geht funktioniert, was $ R $ und $ W $ darstellen sollen … kann jemand erklären? Oder vielleicht, wenn Sie einen anderen Algorithmus vorschlagen möchten?
Antwort
Es wäre schön, wenn Sie das Problem angeben würden. Ich gehe davon aus, dass Sie $ n $ -Elemente $ x_i $ haben, die jeweils einen Gewinn $ p_i $ und weight $ w_i $ . Sie möchten Ihren Gewinn unter der Bedingung maximieren, dass das Gesamtgewicht höchstens $ W $ beträgt. Für jedes Element $ x_i $ dürfen Sie einen beliebigen Bruch $ \ theta \ in [0,1] $
Hier ist ein Beispiel. Sie haben rohes Gold mit einem Gewinn von $ 1000 $ und einem Gewicht von $ 1 $ . Sie haben auch Bananen mit einem Gewinn von $ 1 $ und einem Gewicht von $ 10 $ . Angenommen, Sie können ein Gewicht von $ 2 $ tragen. Was würden Sie tun? Natürlich würden Sie zuerst so viel Gold wie möglich einsetzen – nämlich alles, und dann so viele Bananen wie möglich – nämlich ein Zehntel davon, mit einem Gesamtgewinn von $ 1000.1 $ .
Der allgemeine Algorithmus ist ähnlich. Angenommen, Sie teilen $ W $ in einen $ 1000 $ „Slots“, den Sie am meisten füllen möchten profitable Artikel-Gewichtsteile $ W / 1000 $ . Für einen Gegenstand mit einem Gewicht von $ w_i $ haben wir $ w_i / (W / 1000) $ -Stücke (angenommen) für den Moment, in dem dies eine ganze Zahl ist) und jeder von ihnen ist $ p_i / (w_i / (W / 1000)) $ wert. Wenn wir auswählen, was in einen Slot gesteckt werden soll, möchten wir unseren Gewinn maximieren. Daher wählen wir den Artikel mit maximalem $ p_i / w_i $ aus und setzen ihn so viele wie möglich Stücke wie möglich. Wenn wir keinen Platz mehr haben, wählen wir das Element mit dem nächstgrößeren $ p_i / w_i $ usw. aus.
Sie können dies ohne Teilen implementieren $ W $ in ein $ 1000 $ -Stück: Wählen Sie das Element mit maximalem $ p_i / w_i $ und geben Sie so viel wie möglich davon ein. Wenn Sie keinen mehr haben, wählen Sie den nächsten aus und geben Sie so viel wie möglich davon ab. Und so weiter. Um diesen Algorithmus zu implementieren, muss die Liste $ p_i / w_i $ sortiert werden. Dies dauert einige Zeit. $ O (n \ log n) $ . Der von Ihnen beschriebene Algorithmus verwendet denselben Trick, der bei der Schnellauswahl verwendet wird, um die Laufzeit auf $ O (n) $ zu reduzieren, auf Kosten der zufälligen Erstellung des Algorithmus.
Ich schlage den folgenden Weg vor, um den Algorithmus zu verstehen:
- Verstehen Sie den klassischen Greedy-Algorithmus für fraktionierten Rucksack.
- Verstehen Sie die Schnellauswahl.
- Sehen Sie, wie der von Ihnen zitierte Algorithmus die Technik der Schnellauswahl mit dem gierigen Ansatz kombiniert.
Antwort
R ist der Satz von Verhältnissen von Gewinn / Gewicht jedes Objekts , wobei Gewinn und Gewicht von Objekten angegeben sind. Und W ist die Kapazität des Rucksacks .
Anstatt ein zufälliges Element in einem Schritt auszuwählen, können wir den Median-Finding-Algorithmus anwenden Finden Sie den Median in O (n) Zeiten.
Und dann können wir den Rest aller Schritte ausführen.Die Zeitkomplexitätsanalyse lautet also:
T (n) = T (n / 2) + O (n).
Und wir werden O (n) als Lösung erhalten. Sagen Sie mir, wenn etwas nicht richtig erklärt wurde und Sie etwas mehr wissen möchten.
Antwort
In linearer Zeit finden Sie die Medianwert in Bezug auf den Wert pro Gewichtseinheit. Dann können Sie auch in linearer Zeit herausfinden, ob Sie alle Gegenstände, die mindestens so wertvoll sind, in den Rucksack passen oder nicht. Wenn Sie können, tun Sie dies und lösen Sie dieses Problem rekursiv für die n / 2 Elemente mit niedrigerem Wert, vorausgesetzt, Sie “ Haben Sie den Rucksack bereits gefüllt. Wenn Sie „t“ können, können Sie die n / 2 Elemente mit niedrigerem Wert wegwerfen. Versuchen Sie dann erneut, das Problem nur mit den Elementen n / 2 mit dem höchsten Wert zu lösen.
Die Wiederholung hier ist T (n) = T (n / 2) + O (n) , und wir haben das T (n) = O (n) , wie gewünscht.
In der Lösung, die Sie eingefügt haben: R ist die Menge der Verhältnisse, Gewinn / Gewicht W ist die Summe des gesamten Gewichts dieser Menge , verwendet, um mit der Kapazität Ihres Rucksacks zu vergleichen. In ähnlicher Weise repräsentiert {pi / wi | pi / wi} die i-ten Elemente, deren Gewinn dem i-ten Gewichtswert entspricht. Wir vergleichen diesen Wert mit dem zufällig ausgewählten r -Wert und trennen ihn dann basierend auf dem Vergleich des Verhältnisses. Die R1, R2, R3 sind weitere Teilmengen des eingestellten Verhältnisses, abhängig davon, ob das Verhältnis kleiner, gleich oder größer als das von ist das Medianelement.
In ähnlicher Weise sind die W1, W2, W3 die Summe der Gewichte dieser Sätze.
Wählen Sie nun den geeigneten Lösungssatz in Abhängigkeit von den Verhältniswerten aus, wie zu Beginn erläutert.