Rozdělení

O(n·sum)

Problém rozdělení se ptá, zda lze multimnožinu kladných celých čísel rozdělit na dvě skupiny se stejnými součty. To jde právě tehdy, je-li celkový součet sudý a nějaká podmnožina dá dohromady polovinu celku — takže se redukuje na součet podmnožiny s cílem = celek / 2. Tabulka dp[i][s] značí, zda nějaká podmnožina prvních i čísel dává součet s; každá buňka dosáhne s buď bez aktuálního čísla (řádek nad), nebo s ním (řádek nad, posunutý vlevo o číslo). Je-li celek lichý, žádné dělení nefunguje a odpověď je okamžitá. Je to klasický NP-těžký problém s tímhle pseudopolynomiálním řešením, stojí za férovým dělením i vyvažováním zátěže.

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

Jak to funguje

  1. Sečti čísla; je-li celek lichý, rovné dělení neexistuje.
  2. Jinak miř na polovinu celku a vyplň tabulku součtu podmnožiny.
  3. Každá buňka: dosažitelné bez tohoto čísla, nebo s ním (posunuté vlevo o jeho hodnotu).
  4. Je-li buňka vpravo dole (součet = polovina) dosažitelná, sada se dělí na půl.

Pseudokód

1partition(nums):                    # O(n·sum)2  total ← sum(nums)3  if total is odd: return false4  half ← total / 25  subset-sum DP: can some subset reach `half`?6    dp[i][s] ← dp[i-1][s] or dp[i-1][s-nums[i]]7  return dp[n][half]                 # split exists ⇔ true