Subset Sum Problem

Q: Jaki związek ma problem sumy podzbioru z problemem podziału na równe podzbiory i problemem plecakowym 0/1?

Partition Equal Subset Sum to Subset Sum z wartością target = total / 2 , po sprawdzeniu, czy suma jest parzysta. Subset Sum to plecak 0/1, w którym każda wartość jest jednocześnie własną wagą, a plecak musi być wypełniony dokładnie, więc tabela przechowuje wartości logiczne zamiast najlepszych wartości.

Q: Jak znaleźć wartości, które dają wynik docelowy?

Zachowaj całą tablicę i zacznij od made[n][target] . Przechodź o jeden wiersz w górę naraz: jeśli made[i-1][s] ma wartość true, nums[i-1] nie było potrzebne; w przeciwnym razie zapisz je i odejmij od s . Zatrzymaj się, gdy suma wyniesie 0 — wtedy masz jeden prawidłowy wybór.

ŚrednieProgramowanie dynamiczne

+10

nums zawiera dodatnie liczby całkowite, a target jest dodatnią liczbą całkowitą. Czy możesz wybrać niektóre wartości, każdą pozycję najwyżej raz, tak aby ich suma wynosiła dokładnie target? Zwróć true, jeśli jest to możliwe, i false, jeśli żaden wybór nie zadziała.

Funkcja

isSubsetSum(nums: integer-array, target: integer) → boolean

numsinteger-array: dodatnie wartości, które możesz wybrać
targetinteger: dokładna suma, do której muszą się równać wybrane wartości
Zwracaboolean: true, gdy niektóre wartości sumują się dokładnie do target, w przeciwnym razie false

Ograniczenia

1 ≤ nums.length ≤ 200
1 ≤ nums[i] ≤ 10⁴
1 ≤ target ≤ 10⁴

Przykłady

Wejście: nums = [8, 3, 11, 5, 7]target = 15
Wyjście: true
Wyjaśnienie: 8 + 7 = 15, więc odpowiedź to true. Wybór 3 + 5 + 7 też działa; wystarczy jeden wybór.

Wejście: nums = [6, 9, 12, 15]target = 20
Wyjście: false
Wyjaśnienie: Każda wartość jest wielokrotnością 3, więc każda ich suma również jest wielokrotnością 3. 20 nią nie jest, więc odpowiedź to false.

Wejście: nums = [4, 1, 2]target = 8
Wyjście: false
Wyjaśnienie: Wszystkie trzy wartości razem dają 4 + 1 + 2 = 7, czyli mniej niż 8, więc żaden wybór nie może osiągnąć tej wartości, a odpowiedź to false.

Pytanie dodatkowe

Dwie równe wartości na różnych pozycjach są liczone jako różne wybory. Ile wyborów daje target?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Każda wartość może zostać wybrana albo nie, więc dla 200 wartości istnieje 2^200 możliwości wyboru. Liczą się jednak tylko sumy do target ≤ 10^4. Zapisz, jakie sumy można uzyskać z dotychczasowych wartości: każda nowa wartość przesuwa ten zapis o swoją wielkość, a wyszukiwanie sprowadza się do tabeli n × target wartości logicznych.

Weź lub pomiń każdą wartość

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

Intuicja

canMake(i, remaining) sprawdza, czy wartości od pozycji i mogą dać dokładnie remaining. Wybierz nums[i], jeśli się mieści — wtedy dla pozostałych zostaje remaining-nums[i]; jeśli to się nie powiedzie, pomiń tę wartość. Każdy wybór to jedna ścieżka, więc wyszukiwanie znajdzie wybór, jeśli taki istnieje.

Gdy żaden nie istnieje, algorytm przechodzi przez wszystkie możliwości. Przy 200 wielokrotnościach 3, każdej nie większej niż 300, i celu równym 9998 żaden wybór nie działa, a dowolne 33 wartości pozostają poniżej celu: ponad 10^37 ścieżek.

Algorytm

Napisz canMake(i, remaining).
Wartość remaining równa 0 oznacza, że wybór jest zakończony: zwróć true. Jeśli nie ma już żadnych wartości, a nadal coś trzeba utworzyć, zwróć false.
Jeśli nums[i] ≤ remaining i canMake(i+1, remaining-nums[i]) zwraca true, zwróć true.
W przeciwnym razie zwróć canMake(i+1, remaining).
Zwróć canMake(0, target).

def isSubsetSum(nums, target):
    n = len(nums)

    # Can some of nums[i], nums[i+1], ... add up to exactly remaining?
    def can_make(i, remaining):
        if remaining == 0:
            return True
        if i == n:
            return False
        if nums[i] <= remaining and can_make(i + 1, remaining - nums[i]):
            return True  # take nums[i]
        return can_make(i + 1, remaining)  # skip it

    return can_make(0, target)

Wypełnij tabelę osiągalnych sum

Intuicja

Rekurencja zależy tylko od pozycji i pozostałej sumy z zakresu od 0 do target, a wiele ścieżek prowadzi do tej samej pary. Zamiast tego wypełnij tabelę. made[i][s] ma wartość true, gdy wybór spośród pierwszych i wartości daje dokładnie sumę s; pusty wybór daje 0. Przy num = nums[i-1] suma s jest osiągalna, jeśli była osiągalna bez num, czyli made[i-1][s], albo jeśli num dopełnia s-num, czyli made[i-1][s-num], przy s ≥ num.

W pierwszym przykładzie po 8 osiągalne sumy to 0 i 8. 3 dodaje 3 i 11, 11 dodaje tylko 14, 5 dodaje 5 i 13, a 8 + 7 daje 15. Przy maksymalnych ograniczeniach tabela ma 201 × 10001 komórek, czyli około 2 × 10^6 kroków.

Algorytm

Utwórz tablicę made z n+1 wierszami i target+1 wartościami logicznymi, ustawionymi na false. Dla pustego wyboru ustaw made[0][0] na true.
Wiersz i obsługuje wartość num = nums[i-1], dla i = 1 do n.
Dla każdej sumy s od 0 do target ustaw made[i][s] na made[i-1][s].
Jeśli s ≥ num i made[i-1][s-num] ma wartość true, ustaw made[i][s] na true.
Zwróć made[n][target].

def isSubsetSum(nums, target):
    n = len(nums)
    # made[i][s]: some of the first i values add up to exactly s
    made = [[False] * (target + 1) for _ in range(n + 1)]
    made[0][0] = True
    for i in range(1, n + 1):
        num = nums[i - 1]
        for s in range(target + 1):
            # leave num out, or put it in on top of a sum of s-num
            made[i][s] = made[i - 1][s] or (s >= num and made[i - 1][s - num])
    return made[n][target]

Jeden wiersz sum, aktualizowany od góry

Intuicja

Każdy wiersz odczytuje tylko poprzedzający go wiersz, więc może go przechowywać jedna tablica made[s]. Nadpisz ją, idąc w górę, a wartość zacznie zasilać samą siebie: dla nums = [5] i celu 10 wartość s = 5 zmienia się na true, a następnie s = 10 odczytuje ten nowy wpis, używając 5 dwa razy.

Idź od target w dół do num. Odczyt z s-num trafia do niższej komórki, której ten przebieg jeszcze nie nadpisał, więc odczytuje wiersz sprzed uwzględnienia num. Utworzona suma pozostaje utworzona, więc możesz zakończyć od razu, gdy made[target] ma wartość true. Pamięć spada do target + 1 wartości logicznych.

Algorytm

Zacznij od pojedynczej tablicy zawierającej target + 1 wartości logicznych, w której tylko made[0] ma wartość true.
Przetwarzaj wartości po kolei. Dla każdej wartości num odliczaj s w dół od target do num.
W każdym miejscu, w którym made[s-num] ma wartość true, oznacz made[s].
Zwróć true, gdy tylko zostanie oznaczone made[target].
Jeśli wcześniej wykorzystasz wszystkie wartości, odpowiedzią jest false.

def isSubsetSum(nums, target):
    # made[s]: some of the values seen so far add up to exactly s
    made = [False] * (target + 1)
    made[0] = True
    for num in nums:
        # Downward, so made[s - num] still ignores num
        for s in range(target, num - 1, -1):
            if made[s - num]:
                made[s] = True
        if made[target]:
            return True
    return False

Pułapki i przypadki brzegowe

Pętla rosnąca po sumach używa wartości dwukrotnie: [3] z celem 9 zwraca true.
Zapomnienie o made[0] = true. Każda suma bazuje na pustym wyborze, więc każda odpowiedź jest false.
Wybieranie najpierw największych wartości. Dla [6, 5, 5] z celem 10 wybranie 6 pozostawia 4, których nic nie tworzy, podczas gdy 5 + 5 = 10.
Wartość większa od target, jak w przypadku [10000] z celem 1, nie może niczego zmienić. Swiftowe num...target zatrzymuje program, a (num+1):(target+1) w R odlicza wstecz, więc najpierw sprawdź num ≤ target.
W Lua i R wpis dla sumy s znajduje się pod indeksem s + 1.

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu sumy podzbioru?

Tablica wymaga czasu O(n × target), około 2 × 10^6 kroków dla 200 wartości i celu równego 10^4, a jeden wiersz zmniejsza zużycie pamięci do O(target). Koszt zależy od wartości liczbowej celu, więc metoda jest pseudo-wielomianowa i bezużyteczna dla celu takiego jak 10^18. Ogólnie problem sumy podzbioru jest NP-zupełny.

Jaki związek ma problem sumy podzbioru z problemem podziału na równe podzbiory i problemem plecakowym 0/1?

Partition Equal Subset Sum to Subset Sum z wartością target = total / 2, po sprawdzeniu, czy suma jest parzysta. Subset Sum to plecak 0/1, w którym każda wartość jest jednocześnie własną wagą, a plecak musi być wypełniony dokładnie, więc tabela przechowuje wartości logiczne zamiast najlepszych wartości.

Czy problem sumy podzbioru działa dla liczb ujemnych?

Pomysł działa, ale powyższy kod nie. W przypadku liczb ujemnych osiągalne sumy rozciągają się od sumy liczb ujemnych do sumy liczb dodatnich, więc przesuń każdy indeks o tę najmniejszą sumę i wypełnij wiersz w ten sam sposób. Wartości większej niż pozostała suma nie można już pominąć.

Jak znaleźć wartości, które dają wynik docelowy?

Zachowaj całą tablicę i zacznij od made[n][target]. Przechodź o jeden wiersz w górę naraz: jeśli made[i-1][s] ma wartość true, nums[i-1] nie było potrzebne; w przeciwnym razie zapisz je i odejmij od s. Zatrzymaj się, gdy suma wyniesie 0 — wtedy masz jeden prawidłowy wybór.

def isSubsetSum(nums, target):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

nums = [8, 3, 11, 5, 7]
target = 15

Oczekiwany wynik

true

Subset Sum Problem

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Weź lub pomiń każdą wartość

Wypełnij tabelę osiągalnych sum

Jeden wiersz sum, aktualizowany od góry

Pułapki i przypadki brzegowe

Najczęstsze pytania4

Podobne zadania