Rod Cutting Problem

Q: Warum ist das Stabschneiden ein unbeschränktes Rucksackproblem?

Betrachte jede Stücklänge k als Gegenstand mit dem Gewicht k und dem Wert prices[k-1] , von dem es unbegrenzt viele Exemplare gibt, und den Stab als einen Rucksack mit der Kapazität n, der exakt gefüllt werden muss. Der beste Gesamtwert der Gegenstände ist dann der beste Preis für den Stab.

Q: Wie findest du heraus, wo du den Stab schneiden musst?

Speichere für jede Länge das erste Stück k , das den besten Preis erzielt hat. Beginne bei der Länge n: Schneide ein Stück in der gespeicherten Länge ab, gehe zur verbleibenden Länge über und wiederhole den Vorgang, bis sie 0 erreicht. Die Stücke ergeben zusammen einen optimalen Plan.

MittelDynamische Programmierung

+10

Du hast einen Stab der Länge n, wobei n = prices.length gilt. Ein Stück der Länge k lässt sich für prices[k-1] verkaufen. Du kannst den Stab in beliebig viele Stücke mit ganzzahligen Längen schneiden oder ihn als Ganzes verkaufen. Gib den höchstmöglichen Erlös zurück, den du durch den Verkauf des gesamten Stabs erzielen kannst.

Funktion

cutRod(prices: integer-array) → integer

pricesinteger-array: prices[k-1] ist der Preis eines Stücks der Länge k; der Stab ist prices.length lang
Gibt zurückinteger: das meiste Geld, das die gesamte Stange verdienen kann

Einschränkungen

1 ≤ prices.length ≤ 1000
1 ≤ prices[i] ≤ 10⁵

Beispiele

Eingabe: prices = [2, 5, 7, 8]
Ausgabe: 10
Erklärung: Zwei Stücke der Länge 2 verkaufen sich für 5 + 5 = 10. Der Verkauf des ganzen Stabs bringt 8 ein, und ein Stück der Länge 1 plus ein Stück der Länge 3 bringt 2 + 7 = 9 ein.

Weiterführende Frage

Was ist, wenn du den Stab höchstens m-mal schneiden darfst? Was muss dann jeder Tabelleneintrag wissen?

Tipps

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

0 von 3 geöffnet

Lösung

Ein Stab der Länge n lässt sich auf 2^(n-1) Arten zerschneiden. Du brauchst sie nie alle: Egal, wie lang das erste Stück ist, der Rest ist ein kürzerer Stab, der dieselbe Frage stellt. Es gibt also nur n+1 Antworten, eine pro Länge, und wenn man sie von der kürzesten aus berechnet, braucht das O(n²) Schritte.

Probiere jede Länge für das erste Stück aus

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

Idee

Unabhängig vom Plan hat das Stück am linken Ende eine Länge k zwischen 1 und der Länge des Stabs und bringt prices[k-1] ein; der Rest des Plans zerschneidet einen Stab der Länge length-k. Daher ist best(length) für die Länge 0 gleich 0 und andernfalls der größte Wert von prices[k-1] + best(length-k) über alle k, wobei bei k = length der Stab als Ganzes verkauft wird. Jeder Plan hat ein erstes Stück, daher deckt dieses Maximum alle Pläne ab.

Jeder Aufruf verzweigt sich in alle kürzeren Längen, sodass sich die Anzahl der Aufrufe mit jeder Längeneinheit verdoppelt: Ein Stab der Länge 40 führt zu etwa 2^40 oder 10^12 Aufrufen.

Algorithmus

Schreibe best(length), das für die Länge 0 den Wert 0 zurückgibt.
Berechne für jedes erste Stück k von 1 bis length prices[k-1] + best(length-k).
Gib den größten dieser Werte zurück.
Gib best(n) zurück.

def cutRod(prices):
    # The most money a rod of this length can earn
    def best(length):
        top = 0
        for piece in range(1, length + 1):
            # sell a first piece of this length, then cut the rest as well as possible
            top = max(top, prices[piece - 1] + best(length - piece))
        return top

    return best(len(prices))

Bester Preis für jede Länge, beginnend mit der kürzesten

Idee

Die Rekursion berechnet dieselben Werte erneut: best(2) wird von best(3), best(4) und jedem längeren Stab abgefragt. Es gibt nur n+1 Längen, also berechne jede einmal und speichere sie in einem Array best. Für eine Länge werden nur kürzere Längen benötigt. Wenn du das Array also von 0 aufwärts füllst, ist jeder Wert bereit, wenn er gelesen wird.

Bei [2, 5, 7, 8]: best[1] ist 2, best[2] ist der größere Wert aus 2 + 2 und 5, also 5, best[3] ist 7 und best[4] ist der größte Wert aus 2 + 7, 5 + 5, 7 + 2 und 8, also 10.

Anders als beim 0/1-Rucksackproblem kann best[len-k] bereits Stücke der Länge k enthalten. Genau das ist erwünscht, da eine Länge beliebig oft abgeschnitten werden kann. Für die Länge len werden zunächst len Stücke ausprobiert: insgesamt n(n+1)/2 Schritte, also etwa 5 × 10^5 bei einem Stab der Länge 1000.

Algorithmus

Erstelle best mit n + 1 Einträgen, alle auf 0 gesetzt.
Probiere für jede length von 1 bis n jedes erste Stück k von 1 bis length aus.
Berechne prices[k-1] + best[length-k] und speichere den größten Wert in best[length].
Gib best[n] zurück.

def cutRod(prices):
    n = len(prices)
    # best[length]: the most money a rod of that length can earn
    best = [0] * (n + 1)
    for length in range(1, n + 1):
        for piece in range(1, length + 1):
            # a first piece of this length, then the best for what is left
            earned = prices[piece - 1] + best[length - piece]
            if earned > best[length]:
                best[length] = earned
    return best[n]

Stolperfallen und Grenzfälle

prices[k] für die Länge k auslesen. Dadurch wird jedes Stück eine Längeneinheit zu lang berechnet und bei k = n über das Ende hinaus zugegriffen; verwende prices[k-1].
k = length, das ungeschnittene Stück, auslassen. Dann bleibt best[1] bei 0, und [1, 3, 8] erzielt 3 statt 8.
Gierig nach dem besten Preis pro Längeneinheit schneiden. Bei [2, 7, 11, 13] bringt Länge 3 den höchsten Preis pro Längeneinheit, aber 11 dafür plus 2 für den Rest ergibt 13, während zwei Stücke der Länge 2 zusammen 14 ergeben.
In Python Top-down-Memoisierung verwenden. Die Rekursion verschachtelt sich weiterhin so tief, wie die Stange lang ist: Bei einer Stange der Länge 1000 sind es 1001 verschachtelte Aufrufe und damit mehr als das Standardlimit von 1000. Fülle das Array Bottom-up.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität des Problems des Stabschneidens?

Die Tabelle benötigt O(n²) Zeit und O(n) Speicherplatz: Die Länge len versucht len erste Stücke, insgesamt n(n+1)/2 Versuche. Ohne gespeicherte Ergebnisse führt die Rekursion bei einer Stange der Länge n genau 2^n Aufrufe aus, da jede Länge alle kürzeren Längen aufruft.

Warum ist das Stabschneiden ein unbeschränktes Rucksackproblem?

Betrachte jede Stücklänge k als Gegenstand mit dem Gewicht k und dem Wert prices[k-1], von dem es unbegrenzt viele Exemplare gibt, und den Stab als einen Rucksack mit der Kapazität n, der exakt gefüllt werden muss. Der beste Gesamtwert der Gegenstände ist dann der beste Preis für den Stab.

Wie findest du heraus, wo du den Stab schneiden musst?

Speichere für jede Länge das erste Stück k, das den besten Preis erzielt hat. Beginne bei der Länge n: Schneide ein Stück in der gespeicherten Länge ab, gehe zur verbleibenden Länge über und wiederhole den Vorgang, bis sie 0 erreicht. Die Stücke ergeben zusammen einen optimalen Plan.

Wie ändert sich die Lösung, wenn jeder Schnitt Geld kostet?

Wird die Stange als Ganzes verkauft, ist kein Schnitt nötig, während jedes andere erste Stück einen Schnitt erfordert. Daher wird best[len] zum größeren Wert aus prices[len-1] und dem größten Wert von prices[k-1] + best[len-k] - cost für k kleiner als len. Der Rest der Tabelle bleibt unverändert.

def cutRod(prices):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

prices = [2, 5, 7, 8]

Erwartete Ausgabe