de Fabian Terh

Anterior, am scris despre rezolvarea problemei Knapsack (KP) cu programare dinamică. Puteți citi despre asta aici.

Astăzi vreau să discut o variantă a KP: partiție egală cu problema de sumă de subset. Am văzut prima dată această problemă pe Leetcode – asta m-a determinat să aflu și să scriu despre KP.

Aceasta este declarația problemei (reprodusă parțial fără exemple):

Având în vedere un tablou ne-gol care conține doar numere întregi pozitive, aflați dacă matricea poate fi partiționată în două subseturi astfel încât suma elementelor din ambele subseturi să fie egală.

Pentru declarația completă a problemei, cu constrângeri și exemple, consultați Problemă Leetcode.

Programare dinamică

Ca și în cazul KP, vom rezolva acest lucru folosind programarea dinamică. Deoarece aceasta este o variație a KP, logica și metodologia sunt în mare măsură similare.

Soluţie

Vom adăuga soluția noastră într-o metodă care returnează un boolean – adevărat dacă matricea poate fi partiționată în subseturi egale și falsă în caz contrar.

Pasul 1: Protejarea împotriva sumei matrice impare

În mod trivial, dacă toate numerele din matrice se adună la o sumă impar, putem returna false. Procedăm doar dacă matricea se adaugă la o sumă uniformă.

Pasul 2: Crearea tabelului

Apoi, creăm tabelul.

Rândurile de tabel reprezintă setul de elemente matrice care trebuie luate în considerare, în timp ce coloanele de tabel indică suma la care dorim să ajungem. Valorile tabelului sunt pur și simplu valori booleene, indicând dacă se poate ajunge la o sumă (coloană) cu un set de elemente matrice (rând).

Concret, rând eu reprezintă un set de elemente matrice de la indici 0 la (eu-1). Motivul acestui offset de 1 este că rândul 0 reprezintă un set gol de elemente. Prin urmare, rândul 1 reprezintă primul element de matrice (index 0), rândul 2 reprezintă primele două elemente de matrice (indici 0-1) și așa mai departe. În total, creăm n + 1 rânduri, inclusiv 0.

Vrem să știm doar dacă putem însuma exact până la jumătate din suma totală a matricei. Deci, trebuie doar să creăm totalSum / 2 + 1 coloane, inclusiv 0.

Pasul 3: Preumplerea mesei

Putem începe imediat să completăm intrările pentru cazurile de bază din tabelul nostru – rândul 0 și coloana 0.

În primul rând, fiecare intrare – cu excepția primei – trebuie să fie false. Amintiți-vă că primul rând reprezintă un set gol. Bineînțeles, nu putem ajunge la nicio sumă țintă – numărul coloanei – cu excepția 0.

În prima coloană, fiecare intrare trebuie să fie true. Putem oricând, în mod banal, să ajungem la o sumă țintă de 0, indiferent de setul de elemente cu care trebuie să lucrăm.

Pasul 4: Construirea mesei (esența problemei)

Unele intrări în tabel la rând eu și coloană j este true (realizabil) dacă una dintre următoarele trei condiții este îndeplinită:

  1. intrarea la rând eu-1 și coloană j este true. Reamintim ce reprezintă numărul rândului. Prin urmare, dacă suntem capabili să obținem o anumită sumă cu un subset de elemente pe care le avem în prezent, putem atinge suma respectivă cu setul nostru actual de elemente – prin simpla neutilizare a elementelor suplimentare. Acest lucru este banal. Să numim asta prevRowIsTrue.
  2. Elementul actual este exact suma pe care dorim să o obținem. Acest lucru este, de asemenea, trivial adevărat. Să numim asta isExactMatch.
  3. Dacă cele două condiții de mai sus nu sunt îndeplinite, mai avem un mod de a atinge suma țintă. Aici, folosim elementul curent – elementul suplimentar din setul de elemente din rândul nostru curent comparativ cu setul de elemente din rândul anterior – și verificăm dacă suntem capabili să obținem restul sumei țintă. Să numim asta canArriveAtSum.

Să despachetăm condiția 3. Putem folosi doar elementul curent dacă este mai mică decât suma țintă. Dacă sunt egale, condiția 2 ar fi îndeplinită. Dacă este mai mare, nu îl putem folosi. Prin urmare, primul pas este să vă asigurați că elementul actual

După utilizarea elementului nostru curent, rămânem cu restul sumei țintă. Apoi verificăm dacă acest lucru este realizabil verificând intrarea corespunzătoare din rândul de mai sus.

Ca și în cazul KP obișnuit, dorim să ne construim progresiv masa de jos în sus. Începem cu cazurile de bază, până ajungem la soluția noastră finală.

Pasul 5: returnarea răspunsului

Pur și simplu ne întoarcem return mat[nums.length][totalSum / 2].

Cod de lucru

Mulțumesc pentru lectură!