Variace problému Knapsack: jak vyřešit problém rozdělení oddílů Equal Subset Sum v Javě

Aktualizace: Přečtěte si o optimalizaci prostorové složitosti dynamického programovacího řešení v mém navazujícím článku zde.

Dříve jsem psal o řešení problému Knapsack (KP) s dynamickým programováním. Můžete si o tom přečíst zde.

Dnes chci diskutovat o variantě KP: problém se stejným dílčím součtem. Poprvé jsem viděl tento problém na Leetcode - to bylo to, co mě přimělo učit se o KP a psát o něm.

Toto je prohlášení o problému (částečně reprodukováno bez příkladů):

Vzhledem k neprázdnému poli obsahujícímu pouze kladná celá čísla zjistěte, zda lze pole rozdělit do dvou podmnožin tak, aby součet prvků v obou podmnožinách byl stejný.

Úplné prohlášení o problému s omezeními a příklady najdete v tématu Problém s kódem Leetcode.

Dynamické programování

Stejně jako u KP to vyřešíme pomocí dynamického programování. Protože se jedná o variantu KP, je logika a metodika do značné míry podobné.

Řešení

Budeme umístit naše řešení metodou, která vrací booleovské hodnoty - true, pokud lze pole rozdělit do stejných podmnožin a jinak falešné.

Krok 1: Ochrana před součtem lichých polí

Triviálně, pokud všechna čísla v poli sečtou k liché sumě, můžeme vrátit false. Pokračujeme pouze v případě, že pole sečte až sudou částku.

Krok 2: Vytvoření tabulky

Dále vytvoříme tabulku.

Řádky tabulky představují sadu prvků pole, které je třeba zvážit, zatímco sloupce tabulky označují částku, do které chceme dospět. Hodnoty tabulky jsou jednoduše booleovské hodnoty, což ukazuje, zda lze součtu (sloupce) dosáhnout pomocí sady prvků pole (řádek).

Řádek i konkrétně představuje sadu prvků pole od indexů 0 do (i-1). Důvodem tohoto posunu 1 je, že řádek 0 představuje prázdnou sadu prvků. Řádek 1 proto představuje první prvek pole (index 0), řádek 2 představuje první dva prvky pole (indexy 0–1) atd. Celkem vytváříme n + 1 řádků, včetně 0.

Chceme jen vědět, jestli můžeme sčítat přesně polovinu celkové sumy pole. Potřebujeme tedy vytvořit pouze sloupce totalSum / 2 + 1, včetně 0.

Krok 3: Předplnění stolu

Můžeme okamžitě začít vyplňovat položky pro základní případy v naší tabulce - řádek 0 a sloupec 0.

V prvním řádku musí být každá položka - kromě prvního - nepravdivá. Připomeňme, že první řádek představuje prázdnou sadu. Přirozeně nemůžeme dospět k žádné cílové sumě - číslu sloupce - kromě 0.

V prvním sloupci musí být každá položka pravdivá. Vždy můžeme triviálně dospět k cílové sumě 0, bez ohledu na sadu prvků, se kterými musíme pracovat.

Krok 4: Sestavení stolu (jádro problému)

Nějaký záznam v tabulce na řádku i a sloupci j je pravdivý (dosažitelný), pokud je splněna jedna z následujících tří podmínek:

  1. položka v řádku i-1 a sloupci j je pravdivá. Vzpomeňte si, co číslo řádku představuje. Pokud tedy dokážeme dosáhnout určité částky s podmnožinou prvků, které máme v současné době, můžeme tuto částku také dosáhnout s naší současnou sadou prvků - jednoduše tím, že nepoužijeme další prvky. To je triviální. Řekněme tomu prevRowIsTrue.
  2. Aktuální prvek je přesně suma, kterou chceme dosáhnout. To platí také triviálně. Říkejme tomu isExactMatch.
  3. Pokud výše uvedené dvě podmínky nejsou splněny, máme ještě jeden způsob, jak dosáhnout naší cílové částky. Zde použijeme aktuální prvek - další prvek v sadě prvků v našem aktuálním řádku ve srovnání se sadou prvků v předchozím řádku - a zkontrolujeme, zda jsme schopni dosáhnout zbytku cílové částky. Říkejme tomu canArriveAtSum.

Rozbalme podmínku 3. Aktuální prvek můžeme použít, pouze pokud je menší než naše cílová částka. Pokud jsou si rovni, podmínka 2 by byla splněna. Pokud je větší, nemůžeme ho použít. Prvním krokem je proto zajistit, aby aktuální prvek

Po použití našeho aktuálního prvku nám zbývá zbytek naší cílové částky. Poté zkontrolujeme, zda je to dosažitelné kontrolou příslušného záznamu v řádku výše.

Stejně jako u běžných KP chceme i my postupně sestavovat náš stůl zdola nahoru. Začínáme se základními případy, dokud nedosáhneme konečného řešení.

Krok 5: Vrácení odpovědi

Jednoduše vrátíme návratovou mat [nums.length] [totalSum / 2].

Pracovní kód

Děkuji za přečtení!