Fractional Knapsack

Q: Wie hoch ist die Zeitkomplexität des fractional knapsack problems?

Das Sortieren der Elemente nach Wert pro Gewicht kostet O(n log n) , und das Befüllen erfolgt in einem Durchlauf. Daher beträgt der Gesamtaufwand O(n log n) bei O(n) Speicherplatz für die Reihenfolge. In jeder Runde nach dem Element mit der höchsten Wertdichte zu suchen, kostet O(n²) .

Q: Wie löst man das fraktionale Rucksackproblem ohne Gleitkommazahlen?

Bei positiven Gewichten ist a / b > c / d derselbe Test wie a × d > c × b . Vergleiche daher die Dichten durch Kreuzmultiplikation. Der beste Wert besteht aus einer ganzen Zahl plus einem Bruch, values[i] × room / weights[i] für den angeschnittenen Gegenstand, sodass eine ganzzahlige Division genau das abgerundete Ergebnis liefert.

MittelGreedy Sortieren

+10

Du hast n Gegenstände. Gegenstand i ist values[i] wert und wiegt weights[i]. Dein Rucksack kann insgesamt höchstens ein Gewicht von capacity tragen, und du darfst jeden Gegenstand teilweise mitnehmen: Ein Stück von Gegenstand i mit einem Gewicht von w ist values[i] × w / weights[i] wert.

Schreibe eine Funktion namens fractionalKnapsack, die den größten Gesamtwert zurückgibt, den der Rucksack tragen kann, abgerundet auf eine ganze Zahl.

Funktion

fractionalKnapsack(values: integer-array, weights: integer-array, capacity: integer) → integer

valuesinteger-array: der Wert jedes Elements
weightsinteger-array: das Gewicht jedes Gegenstands
capacityinteger: das höchste Gewicht, das der Rucksack tragen kann
Gibt zurückinteger: der größte Gesamtwert, der in den Rucksack passt, abgerundet

Einschränkungen

1 ≤ n ≤ 5000, wobei n = values.length = weights.length
1 ≤ values[i], weights[i] ≤ 10⁴
1 ≤ capacity ≤ 10⁸

Beispiele

Eingabe: values = [40, 90, 30, 50]weights = [8, 30, 5, 20]capacity = 40
Ausgabe: 151
Erklärung: Pro Gewichtseinheit sind die Gegenstände 5, 3, 6 und 2,5 wert. Die Gegenstände 2 und 0 passen vollständig hinein und ergeben 70, sodass noch Platz für 27 bleibt, und 27 der 30 Einheiten von Gegenstand 1 ergeben zusätzlich 81, also insgesamt 151.

Eingabe: values = [10, 7]weights = [4, 3]capacity = 5
Ausgabe: 12
Erklärung: Gegenstand 0 ist pro Einheit 2,5 wert und Gegenstand 1 etwa 2,33, also wird Gegenstand 0 vollständig für 10 eingepackt. Eine der 3 Einheiten von Gegenstand 1 bringt 7 / 3 hinzu, und 12 und ein Drittel wird auf 12 abgerundet.

Weiterführende Frage

Kannst du die Antwort in O(n) Zeit finden, ohne alle Elemente zu sortieren?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Da du Gegenstände teilen kannst, ist das Problem gierig, anders als beim 0/1-Rucksackproblem: Jede Gewichtseinheit sollte von dem Gegenstand stammen, der pro verbleibender Gewichtseinheit den höchsten Wert hat. Sortiere nach dieser Dichte und fülle den Rucksack der Reihe nach. Vergleiche die Dichten durch Kreuzmultiplikation und runde nur den Gegenstand ab, den du teilst, sodass niemals ein Bruch gespeichert wird.

Wähle in jeder Runde den Gegenstand mit der höchsten Dichte aus

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Fülle den Rucksack vom Gegenstand mit der höchsten Dichte abwärts: Nimm ihn ganz, wenn er hineinpasst, andernfalls nimm den Teil, der den Rucksack füllt, und höre auf. Finde den unbenutzten Gegenstand mit der höchsten Dichte, indem du alle durchgehst und values[i] × weights[j] mit values[j] × weights[i] vergleichst, statt zu dividieren. Bei positiven Gewichten ist das derselbe Test, und beide Produkte bleiben höchstens 10^8.

Die Gegenstände in absteigender Dichte zu nehmen, ist optimal: Wenn eine Ladung ein gewisses Gewicht eines Gegenstands mit geringerer Dichte enthält, während ein Gegenstand mit höherer Dichte noch nicht vollständig enthalten ist, kann der Austausch dieses Gewichts gegen den Gegenstand mit höherer Dichte den Wert nicht verringern. Wiederhole den Austausch, und du erhältst die Ladung mit den Gegenständen in absteigender Dichte.

Bis zu n Runden durchsuchen jeweils die unbenutzten Gegenstände; das ergibt etwa n²/2 = 12.5 Millionen Vergleiche für n = 5000.

Algorithmus

Markiere jeden Gegenstand als unbenutzt und setze room = capacity und total = 0.
Solange noch Platz vorhanden ist, durchsuche die unbenutzten Gegenstände nach dem mit der höchsten Dichte und vergleiche die Dichten durch Kreuzmultiplikation.
Wenn kein Gegenstand mehr übrig ist, halte an. Andernfalls markiere diesen Gegenstand als verwendet.
Wenn er hineinpasst, addiere seinen Wert zu total und ziehe sein Gewicht von room ab. Wenn er nicht hineinpasst, addiere values[i] × room / weights[i] mit ganzzahliger Division und halte an.
Gib total zurück.

def fractionalKnapsack(values, weights, capacity):
    n = len(values)
    used = [False] * n
    total = 0
    room = capacity
    while room > 0:
        best = -1
        for i in range(n):
            # i is denser than best: values[i] / weights[i] > values[best] / weights[best], cross-multiplied
            if not used[i] and (best == -1 or values[i] * weights[best] > values[best] * weights[i]):
                best = i
        if best == -1:
            break  # every item is already in the bag
        used[best] = True
        if weights[best] <= room:
            total += values[best]
            room -= weights[best]
        else:
            total += values[best] * room // weights[best]  # the part that fits, rounded down
            room = 0
    return total

Nach Wert pro Gewicht sortieren

Idee

Der Scan findet immer wieder den Gegenstand mit der höchsten Dichte, aber die Reihenfolge ändert sich zwischen den Durchläufen nie. Sortiere die Gegenstände einmal absteigend nach ihrer Dichte, mit demselben Vergleich durch Kreuzmultiplikation. Gegenstände mit gleicher Dichte können in beliebiger Reihenfolge stehen, da sie pro Einheit gleich viel wert sind.

Nimm Gegenstände ganz, solange sie hineinpassen. Der erste, der nicht hineinpasst, ist der einzige, den du teilen musst: Er erhöht den Wert um values[i] × room / weights[i], und die Ganzzahldivision rundet diesen Wert ab. Alles davor besteht aus ganzen Zahlen, daher ergibt das Runden dieses einen Terms die exakte Antwort. Das Sortieren kostet O(n log n) und das Durchlaufen O(n).

Algorithmus

Erstelle eine Liste der Elementindizes und sortiere sie mithilfe des kreuzmultiplizierten Vergleichs absteigend nach Dichte.
Setze room = capacity und total = 0.
Für jedes Element in dieser Reihenfolge: Falls weights[i] ≤ room, addiere seinen Wert und ziehe sein Gewicht von room ab.
Andernfalls addiere values[i] × room / weights[i] mit ganzzahliger Division und brich ab.
Gib total zurück.

from functools import cmp_to_key


def fractionalKnapsack(values, weights, capacity):
    # a goes before b when values[a] / weights[a] > values[b] / weights[b],
    # tested as values[a] * weights[b] > values[b] * weights[a] to stay in whole numbers.
    def denser_first(a, b):
        return values[b] * weights[a] - values[a] * weights[b]

    order = sorted(range(len(values)), key=cmp_to_key(denser_first))
    total = 0
    room = capacity
    for i in order:
        if weights[i] <= room:
            total += values[i]  # the whole item fits
            room -= weights[i]
        else:
            total += values[i] * room // weights[i]  # the part that fits, rounded down
            break
    return total

Stolperfallen und Grenzfälle

Nur nach Wert oder Gewicht sortieren. Im ersten Beispiel steht der Gegenstand im Wert von 90 nach Dichte nur an dritter Stelle; nimmt man ihn zuerst, bleibt Platz für die Hälfte des Gegenstands im Wert von 50, sodass man 115 statt 151 erhält.
Vor dem Multiplizieren dividieren. Bei einem Wert von 13, einem Gewicht von 7 und einem verfügbaren Platz von 3 ergibt 13 / 7 * 3 bei ganzzahliger Arithmetik 3, während 13 * 3 / 7 den richtigen Wert 5 ergibt.
Davon ausgehen, dass jedes Mal ein Gegenstand geteilt wird. Im dritten Beispiel passt jeder Gegenstand hinein, und die Antwort ist die Summe aller Werte, 13.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität des fractional knapsack problems?

Das Sortieren der Elemente nach Wert pro Gewicht kostet O(n log n), und das Befüllen erfolgt in einem Durchlauf. Daher beträgt der Gesamtaufwand O(n log n) bei O(n) Speicherplatz für die Reihenfolge. In jeder Runde nach dem Element mit der höchsten Wertdichte zu suchen, kostet O(n²).

Warum funktioniert der Greedy-Ansatz beim fractionalKnapsack, aber nicht beim 0/1-Knapsack?

Durch das Teilen kannst du Gewicht eines weniger dichten Gegenstands gegen einen dichteren eintauschen. Ohne Teilen kann ein dichter Gegenstand Platz übrig lassen, den nichts anderes ausfüllt. Bei den Werten 8, 11, 15, den Gewichten 2, 3, 4 und einer Kapazität von 7 nimmt die Auswahl der dichtesten Gegenstände zuerst die Gewichte 2 und 4 für 23, während die Gewichte 3 und 4 den Wert 26 ergeben. Die 0/1-Version erfordert dynamische Programmierung.

Wie löst man das fraktionale Rucksackproblem ohne Gleitkommazahlen?

Bei positiven Gewichten ist a / b > c / d derselbe Test wie a × d > c × b. Vergleiche daher die Dichten durch Kreuzmultiplikation. Der beste Wert besteht aus einer ganzen Zahl plus einem Bruch, values[i] × room / weights[i] für den angeschnittenen Gegenstand, sodass eine ganzzahlige Division genau das abgerundete Ergebnis liefert.

def fractionalKnapsack(values, weights, capacity):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

values = [40, 90, 30, 50]
weights = [8, 30, 5, 20]
capacity = 40

Erwartete Ausgabe