0/1 Knapsack Problem

Q: Jak sprawdzić, które elementy wybrał algorytm plecakowy 0/1?

Zachowaj całą tablicę i prześledź ją wstecz od best[n][capacity] . Jeśli best[i][c] różni się od best[i-1][c] , spakowano element i-1 , więc zapisz go i odejmij jego wagę od c . W przeciwnym razie przejdź do wiersza i-1 , zachowując to samo c .

ŚrednieProgramowanie dynamiczne

+10

Masz n przedmiotów. Przedmiot i waży weights[i] i jest wart values[i]. Twój plecak może pomieścić łączną wagę wynoszącą najwyżej capacity. Każdy przedmiot występuje tylko raz i możesz go albo spakować w całości, albo zostawić. Zwróć największą łączną wartość, jaką możesz spakować.

Funkcja

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

weightsinteger-array: waga każdego elementu
valuesinteger-array: wartość każdego elementu
capacityinteger: maksymalny ciężar, jaki może unieść torba
Zwracainteger: największa łączna wartość przedmiotów, których waga mieści się w pojemności

Ograniczenia

1 ≤ n ≤ 100, gdzie n = weights.length = values.length
1 ≤ weights[i] ≤ 1000
1 ≤ values[i] ≤ 10⁴
1 ≤ capacity ≤ 1000

Przykłady

Wejście: weights = [4, 2, 3, 5]values = [10, 4, 7, 12]capacity = 7
Wyjście: 17
Wyjaśnienie: Przedmioty 0 i 2 ważą 4 + 3 = 7 i są warte 10 + 7 = 17. Spakowanie najpierw przedmiotu o największej wartości (waga 5, wartość 12) pozostawia miejsce tylko na przedmiot 1, co daje 16.

Pytanie dodatkowe

Załóżmy, że pojemność może wynosić nawet 10^9, a suma wartości nie przekracza 10^4. Według czego indeksujesz tablicę?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Żadna zachłanna kolejność nie działa: spakowanie najcenniejszego przedmiotu jako pierwszego daje 16, a nie 17, w pierwszym przykładzie. Najlepsza wartość, jaką można uzyskać od przedmiotu i wzwyż, zależy tylko od i i pozostałego miejsca, które jest liczbą całkowitą nie większą niż 1000. Jedna komórka tabeli na każdą parę daje O(n × capacity), a wystarczy jeden wiersz, jeśli przechodzisz po pojemnościach w dół.

Wypróbuj obie opcje dla każdego elementu

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

Intuicja

Niech best(i, room) oznacza największą wartość przedmiotów od i wzwyż, które można dodać przy room wolnych jednostkach; po ostatnim przedmiocie wynosi 0. Pominięcie przedmiotu i daje best(i+1, room). Spakowanie go, gdy weights[i] ≤ room, daje values[i] + best(i+1, room-weights[i]). Zachowaj większą wartość. Każdy pasujący sposób pakowania jest jedną sekwencją wyborów pakowania i pomijania, a rekurencja wypróbowuje je wszystkie.

Każdy przedmiot podwaja liczbę ścieżek. Gdy wszystkie 100 przedmiotów mieści się razem, jak w przypadku przedmiotów o wadze 10 każdy i torby o pojemności 1000, daje to 2^100 ścieżek.

Algorytm

Napisz best(i, room); zwróć 0, gdy i jest poza ostatnim elementem.
Ustaw skip na best(i+1, room).
Jeśli weights[i] > room, zwróć skip.
W przeciwnym razie zwróć większą z wartości: skip i values[i] + best(i+1, room-weights[i]).
Zwróć best(0, capacity).

def knapsack(weights, values, capacity):
    n = len(weights)

    # The most value items i, i+1, ... can add with room units of weight left
    def best(i, room):
        if i == n:
            return 0
        skip = best(i + 1, room)
        if weights[i] > room:
            return skip
        take = values[i] + best(i + 1, room - weights[i])
        return max(skip, take)

    return best(0, capacity)

Wypełnij tabelę według elementu i pojemności

Intuicja

Rekurencja dociera do tej samej pary (i, room) wieloma ścieżkami. Istnieje najwyżej 101 × 1001, czyli około 10^5 par, więc oblicz każdą z nich tylko raz.

Niech best[i][c] oznacza największą wartość, jaką pierwsze i przedmiotów mogą umieścić w plecaku o pojemności c; wiersz 0 składa się wyłącznie z zer. Dla przedmiotu i-1 o wadze w i wartości v pominięcie go daje best[i-1][c], a umieszczenie go w plecaku, gdy w ≤ c, daje best[i-1][c-w] + v. Wiersz i odczytuje tylko wiersz i-1, więc każdy przedmiot trafia do danej komórki najwyżej raz.

W pierwszym przykładzie przedmiot 2 (waga 3, wartość 7) zwiększa wartość dla pojemności 7 do best[2][4] + 7 = 17. Przedmiot 3 daje następnie tylko best[3][2] + 12 = 16, więc odpowiedź pozostaje równa 17.

Algorytm

Utwórz tablicę o n+1 wierszach i capacity+1 kolumnach, wypełnioną zerami.
Dla każdego wiersza i od 1 do n pobierz w = weights[i-1] oraz v = values[i-1].
Dla każdej pojemności c ustaw best[i][c] na best[i-1][c].
Jeśli w ≤ c i best[i-1][c-w] + v jest większe, zapisz zamiast tego tę wartość.
Zwróć best[n][capacity].

def knapsack(weights, values, capacity):
    n = len(weights)
    # best[i][c]: the most value from the first i items within capacity c
    best = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(capacity + 1):
            best[i][c] = best[i - 1][c]  # leave item i-1 out
            if w <= c and best[i - 1][c - w] + v > best[i][c]:
                best[i][c] = best[i - 1][c - w] + v  # put it in
    return best[n][capacity]

Jeden wiersz, pojemności uporządkowane malejąco

Intuicja

Wiersz i potrzebuje tylko wiersza i-1, więc zachowaj jeden wiersz best[c] i nadpisuj go dla kolejnych przedmiotów. Kierunek przechodzenia decyduje o tym, czy odpowiedź będzie poprawna.

Przechodząc w górę po c, best[c-w] może już uwzględniać bieżący przedmiot. Jeden przedmiot o wadze 3 i wartości 5 przy pojemności 6 sprawia, że pojemność 3 ma wartość 5, a następnie pojemność 6 odczytuje tę wartość i zmienia ją na 10: to dwa egzemplarze. Przechodząc w dół od capacity do w, odczytywana komórka znajduje się poniżej tej, którą zapisujesz, i zostanie nadpisana później, więc nadal zawiera wartość z poprzedniego wiersza.

Przechodzenie w górę to właściwa pętla, gdy przedmioty są dostępne w nieograniczonej liczbie egzemplarzy. W tym przypadku czas nadal wynosi O(n × capacity), a pamięć spada do jednego wiersza.

Algorytm

Utwórz best z capacity + 1 wpisami, wszystkie równe 0.
Dla każdego przedmiotu o wadze w i wartości v przechodź przez c od capacity w dół do w.
Jeśli best[c-w] + v jest większe niż best[c], zapisz tę wartość w best[c].
Zwróć best[capacity].

def knapsack(weights, values, capacity):
    # best[c]: the most value from the items seen so far within capacity c
    best = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        # Walk the capacities downward so each item goes in at most once
        for c in range(capacity, w - 1, -1):
            if best[c - w] + v > best[c]:
                best[c] = best[c - w] + v
    return best[capacity]

Pułapki i przypadki brzegowe

Przechodzenie po pojemnościach rosnąco w wersji z jednym wierszem pakuje przedmiot dwukrotnie: jeden przedmiot o wadze 3 i wartości 5 w plecaku o pojemności 6 daje wynik 10 zamiast 5.
Wiersz zawierający capacity elementów zamiast capacity + 1. Zwrócenie best[capacity-1] powoduje utratę każdego upakowania, które dokładnie wypełnia plecak, takiego jak przedmiot o wadze 1 w plecaku o pojemności 1.
Rozpoczynanie od wartości minus nieskończoność. Plecak nie musi być pełny, więc każdy element zaczyna się od 0; przy minus nieskończoności trzeci przykład zwraca minus nieskończoność zamiast 0.
Przedmiot cięższy niż plecak należy pominąć. W trzecim przykładzie zamknięty zakres w...capacity zatrzymuje program w Swift, a (w+1):(capacity+1) odlicza wstecz w R.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu plecakowego 0/1?

Wersja z tablicą działa w czasie O(n × capacity), czyli około 10^5 kroków dla 100 elementów i pojemności 1000, a wersja jednowierszowa zużywa O(capacity) pamięci. Ograniczenie jest pseudowielomianowe: rośnie wraz z wartością pojemności, a nie z liczbą jej cyfr. Ogólny problem jest NP-trudny.

Dlaczego algorytm zachłanny nie działa w problemie plecakowym 0/1?

Chciwa reguła nigdy nie cofa wyboru, nawet gdy przedmiot pozostawia wolne miejsce, którego nic nie wypełnia. Przy pojemności 7 przedmiot o wadze 5 i wartości 10 ma najlepszy stosunek wartości do wagi, ale przedmioty o wadze 4 i 3 są razem warte 13. Zachłanny wybór według stosunku wartości do wagi jest optymalny tylko w przypadku problemu plecakowego ułamkowego, w którym można dzielić przedmioty.

Jak sprawdzić, które elementy wybrał algorytm plecakowy 0/1?

Zachowaj całą tablicę i prześledź ją wstecz od best[n][capacity]. Jeśli best[i][c] różni się od best[i-1][c], spakowano element i-1, więc zapisz go i odejmij jego wagę od c. W przeciwnym razie przejdź do wiersza i-1, zachowując to samo c.

def knapsack(weights, values, capacity):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

weights = [4, 2, 3, 5]
values = [10, 4, 7, 12]
capacity = 7

Oczekiwany wynik

0/1 Knapsack Problem

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Wypróbuj obie opcje dla każdego elementu

Wypełnij tabelę według elementu i pojemności

Jeden wiersz, pojemności uporządkowane malejąco

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania