Varijacija problema s naprtnjačama: kako riješiti problem Partition Equal Subset Sum u Javi

Prije sam pisao o rješavanju problema s naprtnjačom (KP) dinamičkim programiranjem. O tome možete pročitati ovdje.

Danas želim razgovarati o varijaciji KP-a: problem zbroja podskupa jednak particiji. Taj sam problem prvi put vidio na Leetcodeu - upravo me to potaknulo da učim i pišem o KP-u.

Ovo je izjava problema (reproducirana djelomično bez primjera):

S obzirom na neprazan niz koji sadrži samo pozitivne cijele brojeve, pronađite može li se niz podijeliti u dva podskupa tako da je zbroj elemenata u oba podskupa jednak.

Potpunu izjavu problema, s ograničenjima i primjerima, pogledajte u Leetcode problemu.

Dinamičko programiranje

Kao i kod KP, i ovo ćemo rješavati pomoću dinamičkog programiranja. Budući da je ovo varijacija KP-a, logika i metodologija uvelike su slični.

Riješenje

Naše ćemo rješenje smjestiti u metodu koja vraća logičku vrijednost - true ako se niz može podijeliti na jednake podskupove, a false u suprotnom.

Korak 1: Zaštita od neparne sume niza

Trivijalno je da ako se svi brojevi u polju zbroje neparni zbroj, možemo vratiti false. Nastavljamo samo ako se niz zbraja na paran zbroj.

Korak 2: Izrada tablice

Dalje kreiramo tablicu.

Redovi tablice predstavljaju skup elemenata polja koji se trebaju uzeti u obzir, dok stupci tablice označavaju zbroj do kojeg želimo doći. Vrijednosti tablice su jednostavno logičke vrijednosti koje ukazuju na to može li se doći do zbroja (stupca) sa skupom elemenata niza (redak).

Konkretno, redak i predstavlja skup elemenata niza od indeksa 0 do ( i -1). Razlog ovog pomaka 1 je taj što redak 0 predstavlja prazan skup elemenata. Stoga redak 1 predstavlja prvi element niza (indeks 0), red 2 predstavlja prva dva elementa niza (indeksi 0–1) itd. Ukupno izrađujemo n + 1retke, uključujući 0.

Samo želimo znati možemo li zbrojiti točno polovicu ukupnog zbroja niza. Dakle, trebamo stvoriti samo totalSum / 2 + 1stupce, uključujući 0.

Korak 3: Prethodno popunjavanje tablice

Odmah možemo početi popunjavati unose za osnovne slučajeve u našoj tablici - redak 0 i stupac 0.

U prvom redu mora biti svaki unos - osim prvog false. Podsjetimo da prvi redak predstavlja prazan skup. Naravno, nismo u mogućnosti doći do bilo kojeg ciljanog zbroja - broja stupca - osim 0.

U prvom stupcu svaki unos mora biti true. Uvijek možemo trivijalno doći do ciljane sume od 0, bez obzira na skup elemenata s kojima moramo raditi.

Korak 4: Izrada tablice (srž problema)

Neki unos u tablici u retku i i stupcu j je true(ostvariv) ako je zadovoljen jedan od sljedeća tri uvjeta:

  1. unos u retku i -1 i stupcu j je true. Sjetite se što predstavlja broj retka. Stoga, ako smo u mogućnosti postići određeni zbroj s podskupom elemenata koje trenutno imamo, taj zbroj možemo postići i s našim trenutnim skupom elemenata - jednostavno ne koristeći dodatne elemente. Ovo je trivijalno. Nazovimo ovo prevRowIsTrue.
  2. Trenutni je element upravo zbroj koji želimo postići. To je također trivijalno točno. Nazovimo ovo isExactMatch.
  3. Ako gornja dva uvjeta nisu zadovoljena, preostaje nam još jedan način postizanja ciljane svote. Ovdje koristimo trenutni element - dodatni element u skupu elemenata u našem trenutnom retku u usporedbi sa skupom elemenata u prethodnom retku - i provjeravamo možemo li postići ostatak ciljanog zbroja. Nazovimo ovo canArriveAtSum.

Otpakirajmo uvjet 3. Trenutačni element možemo koristiti samo ako je manji od ciljane sume. Ako su jednaki, uvjet 2 bio bi zadovoljen. Ako je veći, ne možemo ga koristiti. Stoga je prvi korak osigurati da trenutni element <ciljni zbroj.

Nakon upotrebe trenutnog elementa, ostaje nam ostatak ciljanog zbroja. Zatim provjeravamo je li to moguće postići provjerom odgovarajućeg unosa u gornjem retku.

Kao i kod redovnog KP-a, i mi želimo postupno graditi svoju tablicu odozdo prema gore. Počinjemo s osnovnim slučajevima, dok ne dođemo do našeg konačnog rješenja.

Korak 5: Vraćanje odgovora

Jednostavno se vraćamo return mat[nums.length][totalSum / 2].

Radni kod

Hvala na čitanju!