Rod Cutting Problem

Q: Jaka jest złożoność czasowa problemu cięcia pręta?

Tablica wymaga czasu O(n²) i pamięci O(n): długość len sprawdza len możliwych długości pierwszego kawałka, czyli łącznie n(n+1)/2 prób. Bez zapamiętanych wyników rekurencja wykonuje dokładnie 2^n wywołań dla pręta o długości n, ponieważ dla każdej długości wywołuje funkcję dla każdej krótszej długości.

Q: Dlaczego problem cięcia pręta jest problemem plecaka bez ograniczeń?

Potraktuj każdy kawałek o długości k jako przedmiot o wadze k i wartości prices[k-1] , dostępny w nieograniczonej liczbie sztuk, a pręt jako plecak o pojemności n, który musi zostać dokładnie wypełniony. Najlepsza łączna wartość przedmiotów jest więc najlepszą ceną pręta.

Q: Jak znaleźć miejsce, w którym należy przeciąć pręt?

Dla każdej długości przechowuj pierwszy kawałek k , który zapewnił jej najlepszą cenę. Zacznij od długości n: odetnij kawałek o zapisanej długości, przejdź do pozostałej długości i powtarzaj, aż osiągnie 0. Kawałki tworzą jeden optymalny plan.

ŚrednieProgramowanie dynamiczne

+10

Masz pręt o długości n, gdzie n = prices.length. Kawałek o długości k można sprzedać za prices[k-1]. Możesz pociąć pręt na dowolną liczbę kawałków o całkowitych długościach albo sprzedać go w całości. Zwróć maksymalną kwotę, jaką możesz zarobić, sprzedając cały pręt.

Funkcja

cutRod(prices: integer-array) → integer

pricesinteger-array: prices[k-1] to cena kawałka o długości k; pręt ma długość prices.length
Zwracainteger: najwięcej pieniędzy, jakie może zarobić cała wędka

Ograniczenia

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

Przykłady

Wejście: prices = [2, 5, 7, 8]
Wyjście: 10
Wyjaśnienie: Dwa kawałki o długości 2 sprzedają się za 5 + 5 = 10. Sprzedaż całego pręta przynosi 8, a kawałek o długości 1 i kawałek o długości 3 przynoszą 2 + 7 = 9.

Pytanie dodatkowe

Co jeśli możesz przeciąć pręt co najwyżej m razy? Co w takim razie musi uwzględniać każdy wpis w tabeli?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Pręt o długości n można pociąć na 2^(n-1) sposobów. Nigdy nie potrzebujesz ich wszystkich: niezależnie od tego, jaki jest pierwszy kawałek, pozostała część to krótszy pręt, który stawia to samo pytanie. Istnieje więc tylko n+1 odpowiedzi, po jednej dla każdej długości, a wyznaczenie ich od najkrótszej do najdłuższej wymaga O(n²) kroków.

Wypróbuj każdą długość pierwszego elementu

Poprawne, ale nie kończy się na największych testach

Intuicja

Niezależnie od planu kawałek na lewym końcu ma długość k od 1 do długości pręta i przynosi prices[k-1]; pozostała część planu polega na pocięciu pręta o długości length-k. Zatem best(length) wynosi 0 dla długości 0, a w pozostałych przypadkach jest największą wartością prices[k-1] + best(length-k) spośród wszystkich k, przy czym k = length oznacza sprzedaż całego pręta. Każdy plan ma pierwszy kawałek, więc to maksimum uwzględnia każdy plan.

Każde wywołanie rozgałęzia się na wszystkie krótsze długości, więc liczba wywołań podwaja się z każdą jednostką długości: dla pręta o długości 40 powstaje około 2^40, czyli 10^12 wywołań.

Algorytm

Napisz best(length), która zwraca 0 dla długości 0.
Dla każdego pierwszego kawałka k od 1 do length oblicz prices[k-1] + best(length-k).
Zwróć największą z tych wartości.
Zwróć best(n).

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))

Najlepsza cena dla każdej długości, od najkrótszej

Intuicja

Rekurencja ponownie oblicza te same wartości: o best(2) prosi best(3), best(4) i każda dłuższa sztabka. Istnieje tylko n+1 długości, więc oblicz każdą z nich raz i zapisz w tablicy best. Długość odczytuje tylko krótsze długości, dlatego wypełnianie tablicy od 0 w górę oznacza, że każda wartość jest gotowa, gdy zostaje odczytana.

Dla [2, 5, 7, 8]: best[1] wynosi 2, best[2] to większa z wartości 2 + 2 i 5, czyli 5, best[3] wynosi 7, a best[4] to największa z wartości 2 + 7, 5 + 5, 7 + 2 i 8, czyli 10.

W przeciwieństwie do plecaka 0/1, best[len-k] może już zawierać kawałki o długości k i właśnie tego chcesz, ponieważ długość możesz ciąć dowolną liczbę razy. Długość len sprawdza najpierw len kawałków: łącznie n(n+1)/2 kroków, czyli około 5 × 10^5 dla sztabki o długości 1000.

Algorytm

Utwórz tablicę best z n + 1 elementami, wszystkie równe 0.
Dla każdej wartości length od 1 do n wypróbuj każdy pierwszy kawałek k od 1 do length.
Oblicz prices[k-1] + best[length-k] i zachowaj największą wartość w best[length].
Zwróć best[n].

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]

Pułapki i przypadki brzegowe

Odczyt prices[k] dla długości k. W ten sposób każdemu kawałkowi przypisujesz cenę za rozmiar o jeden za długi, a przy k = n wychodzisz poza koniec; użyj prices[k-1].
Pominięcie k = length, czyli nieprzeciętego kawałka. Wtedy best[1] pozostaje równe 0, a [1, 3, 8] daje wynik 3 zamiast 8.
Chciwe cięcie według najlepszej ceny za jednostkę. Dla [2, 7, 11, 13] długość 3 przynosi najwięcej za jednostkę, ale 11 za ten kawałek plus 2 za resztę daje 13, podczas gdy dwa kawałki długości 2 dają 14.
Zapamiętywanie wyników metodą top-down w Pythonie. Rekurencja nadal zagnieżdża się na głębokość równą długości pręta: dla pręta o długości 1000 zagnieżdża 1001 wywołań, przekraczając domyślny limit 1000. Wypełnij tablicę od dołu do góry.

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu cięcia pręta?

Tablica wymaga czasu O(n²) i pamięci O(n): długość len sprawdza len możliwych długości pierwszego kawałka, czyli łącznie n(n+1)/2 prób. Bez zapamiętanych wyników rekurencja wykonuje dokładnie 2^n wywołań dla pręta o długości n, ponieważ dla każdej długości wywołuje funkcję dla każdej krótszej długości.

Dlaczego problem cięcia pręta jest problemem plecaka bez ograniczeń?

Potraktuj każdy kawałek o długości k jako przedmiot o wadze k i wartości prices[k-1], dostępny w nieograniczonej liczbie sztuk, a pręt jako plecak o pojemności n, który musi zostać dokładnie wypełniony. Najlepsza łączna wartość przedmiotów jest więc najlepszą ceną pręta.

Jak znaleźć miejsce, w którym należy przeciąć pręt?

Dla każdej długości przechowuj pierwszy kawałek k, który zapewnił jej najlepszą cenę. Zacznij od długości n: odetnij kawałek o zapisanej długości, przejdź do pozostałej długości i powtarzaj, aż osiągnie 0. Kawałki tworzą jeden optymalny plan.

Jak zmienia się rozwiązanie, jeśli każde cięcie kosztuje?

Sprzedaż pręta w całości nie wymaga cięcia, podczas gdy każda inna pierwsza część wymaga jednego cięcia. Zatem best[len] przyjmuje większą z wartości prices[len-1] oraz największej wartości prices[k-1] + best[len-k] - cost dla k mniejszego niż len. Reszta tabeli pozostaje taka sama.

def cutRod(prices):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argument

prices = [2, 5, 7, 8]

Oczekiwany wynik