Variatsioon seljakotiprobleemist: kuidas lahendada Java-süsteemis jaotuse Equal Subset Sum probleem

Värskendus: dünaamilise programmeerimise lahenduse ruumi keerukuse optimeerimise kohta lugege minu järelmeetmete artiklist siin.

Varem kirjutasin Knapsack Probleemi (KP) lahendamisest dünaamilise programmeerimisega. Selle kohta saate lugeda siit.

Täna tahan arutada KP varianti: partitsiooni võrdse alamhulga summa probleem. Ma nägin seda probleemi esmakordselt Leetcode'is - see ajendas mind KP-d tundma õppima ja sellest kirjutama.

See on probleemideklaratsioon (osaliselt ilma näideteta):

Kui tegemist on mittetühja massiiviga, mis sisaldab ainult positiivseid täisarvu, siis leidke, kas massiivi saab jagada kaheks alamhulgaks nii, et mõlemas alamhulgas oleks elementide summa võrdne.

Probleemi täieliku kirjelduse koos piirangute ja näidetega leiate Leetcode'i probleemist.

Dünaamiline programmeerimine

Nagu KP puhul, lahendame ka selle dünaamilise programmeerimise abil. Kuna see on KP variatsioon, on loogika ja metoodika suuresti sarnased.

Lahendus

Me koondame oma lahenduse meetodiga, mis tagastab tõeväärtuse - tõene, kui massiivi saab jaotada võrdseteks alamhulkadeks, ja vale muul juhul.

1. samm: paaritu massiivi summa eest kaitsmine

Triviaalselt, kui kõik massiivi numbrid moodustavad paaritu summa, võime tagastada vale. Me jätkame ainult siis, kui massiivi annab ühtlase summa.

2. samm: tabeli loomine

Järgmisena loome tabeli.

Tabeli read tähistavad massiivielementide kogumit, samas kui tabeli veerud näitavad summat, kuhu tahame jõuda. Tabeli väärtused on lihtsalt tõeväärtused, mis näitavad, kas summa (veerg) saab kätte massiivi elementide komplektiga (rida).

Konkreetselt esindab rida i maatriksielementide komplekti indeksitest 0 kuni (i-1). Selle nihke 1 põhjus on see, et 0. rida tähistab tühja elementide komplekti. Seetõttu tähistab 1. rida esimest massiivi elementi (indeks 0), 2. rida tähistab kahte esimest massiivi elementi (indeksid 0–1) jne. Kokku loome n + 1 rida, kaasa arvatud 0.

Tahame vaid teada, kas suudame kokku võtta täpselt poole massiivi kogusummast. Seega peame looma ainult veeru totalSum / 2 + 1, kaasa arvatud 0.

3. samm: tabeli eeltäitmine

Saame kohe alustada tabelite põhijuhtude kirjete täitmist - rida 0 ja veerg 0.

Esimeses reas peab iga kanne - välja arvatud esimene - olema vale. Tuletame meelde, et esimene rida tähistab tühja komplekti. Loomulikult ei suuda me jõuda ühelegi sihtsummale - veeru numbrile - välja arvatud 0.

Esimeses veerus peab iga kanne olema tõene. Me võime alati triviaalselt jõuda sihtsummani 0, sõltumata elementide kogumist, millega peame töötama.

4. samm: laua ehitamine (probleemi tuum)

Mõni kanne tabeli i reas ja veerus j on tõene (saavutatav), kui üks järgmistest kolmest tingimusest on täidetud:

  1. kanne reas i-1 ja veerus j on tõene. Tuletage meelde, mida rea ​​number tähistab. Seega, kui me suudame saavutada konkreetse summa mõne olemasoleva elementide alamhulgaga, siis saame selle summa saavutada ka oma praeguse elementide komplektiga - lihtsalt lisaelemente mitte kasutades. See on tühine. Helistame sellele prevRowIsTrue.
  2. Praegune element on täpselt summa, mida me tahame saavutada. See on ka triviaalselt tõsi. Kutsugem seda nimegaExactMatch.
  3. Kui kaks ülaltoodud tingimust ei ole täidetud, on meil üks eesmärk oma sihtsumma saavutamiseks. Kasutame siin praegust elementi - täiendava elemendi praeguses reas olevate elementide komplektis võrreldes eelmise rea elementide komplektiga - ja kontrollime, kas suudame saavutada ülejäänud summa sihtsummast. Helistame sellele canArriveAtSum.

Pakkime lahti pakkimise tingimuse 3. Praegust elementi saame kasutada ainult siis, kui see on väiksem kui meie sihtsumma. Kui nad on võrdsed, oleks 2. tingimus täidetud. Kui see on suurem, ei saa me seda kasutada. Seetõttu on esimene samm tagada, et praegune element

Pärast praeguse elemendi kasutamist jääb meile alles ülejäänud osa meie sihtsummast. Seejärel kontrollime ülaltoodud rea vastavat kannet, kas see on saavutatav.

Nagu tavalise KP puhul, tahame oma lauda järk-järgult üles-üles üles ehitada. Alustame põhijuhtumitest, kuni jõuame lõpliku lahenduseni.

5. samm: vastuse tagastamine

Tagastame lihtsalt tagastamismati [nums.length] [totalSum / 2].

Töökood

Täname, et lugesite!