Součet podmnožiny

O(n·sum)

Subset sum se ptá: může nějaká podmnožina daných čísel dát přesně cílový součet? Každé číslo lze použít nejvýš jednou. Tabulka dp[i][s] je 1, pokud nějaká podmnožina prvních i čísel dává součet s, jinak 0. Každá buňka se dívá na dva případy: dosáhnout s bez aktuálního čísla (buňka přímo nad) nebo s ním (buňka nad, posunutá vlevo o hodnotu čísla). Prázdná podmnožina dává součet 0, což nasadí první sloupec. Vyplnění tabulky je O(n·cíl) a buňka vpravo dole odpoví ano nebo ne. Je to rozhodovací verze rodiny problémů batohu a klasický NP-úplný problém řešený pseudopolynomiálně.

DP tabulka
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Součet 0 je vždy dosažitelný prázdnou podmnožinou — to je základní sloupec.
  2. Pro každou buňku zkopíruj, zda byl součet dosažitelný bez tohoto čísla (řádek nad).
  3. Pokud se číslo vejde, zkontroluj i buňku nad posunutou vlevo o jeho hodnotu.
  4. Označ buňku dosažitelnou, pokud platí jedno z toho; buňka vpravo dole je odpověď.

Pseudokód

1subsetSum(nums, target):            # O(n·target)2  dp[i][0] ← true                    # empty subset sums to 03  for each num i, sum s in 1..target:4    dp[i][s] ← dp[i-1][s]            # without num5    if s ≥ num and dp[i-1][s-num]:6      dp[i][s] ← true                # with num7  return dp[n][target]