A hátizsák-probléma variációja: hogyan lehet megoldani a partíció egyenlő részhalmaz-összeg problémáját a Java-ban

Korábban a Knapsack Problem (KP) dinamikus programozással történő megoldásáról írtam. Itt olvashat róla.

Ma szeretnék megvitatni a KP variációját: a partíció egyenlő részhalmaz összeg problémáját. Először a Leetcode-on láttam ezt a problémát - ez késztetett arra, hogy megismerjem és leírjam a KP-t.

Ez a probléma állítás (részben példák nélkül reprodukálva):

Ha egy nem üres tömböt tartalmaz, amely csak pozitív egész számokat tartalmaz, akkor keresse meg, hogy a tömb felosztható-e két részhalmazra úgy, hogy mindkét részhalmaz elemeinek összege megegyezzen.

A teljes problémameghatározás, korlátozások és példák mellett, tekintse meg a Leetcode problémát.

Dinamikus programozás

A KP-hez hasonlóan ezt is dinamikus programozással oldjuk meg. Mivel ez a KP változata, a logika és a módszertan nagyrészt hasonló.

Megoldás

Megoldásunkat egy olyan módszerrel fogjuk elhelyezni, amely logikai értéket ad vissza - igaz, ha a tömböt egyenlő részhalmazokra lehet felosztani, és hamisak egyébként.

1. lépés: Védelem a páratlan tömbösszeg ellen

Triviálisan, ha a tömb összes száma összeadódik egy páratlan összeggel, akkor hamis értéket adhatunk vissza. Csak akkor folytatjuk, ha a tömb egyenletes összeget ad.

2. lépés: A táblázat létrehozása

Ezután elkészítjük a táblázatot.

A táblázat sorai a figyelembe veendő tömb elemek halmazát képviselik, míg a táblázat oszlopai azt az összeget mutatják, amelyhez el akarunk jutni. A táblázat értékei egyszerűen logikai értékek, jelezve, hogy egy összeg (oszlop) elérhető-e egy tömb elemkészlettel (sor).

Konkrétan az i sor tömbelemek halmazát jelöli a 0 és ( i -1) indexek között . Ennek az 1-es eltolásnak az az oka, hogy a 0. sor üres elemkészletet jelent. Ezért az 1. sor az első tömb elemet (0. index), a 2. sor az első két tömb elemet (0–1 index) stb. Összességében n + 1sorokat hozunk létre , beleértve a 0-t is.

Csak azt szeretnénk tudni, hogy a tömb teljes összegének pontosan a felére tudunk-e összegezni. Tehát csak totalSum / 2 + 1oszlopokat kell létrehoznunk , beleértve a 0-t is.

3. lépés: Töltse ki a táblázatot

Azonnal elkezdhetjük kitölteni a táblázatunk alapeseteinek bejegyzéseit - 0. sor és 0. oszlop.

Az első sorban minden bejegyzésnek szerepelnie kell - az első kivételével false. Emlékezzünk arra, hogy az első sor üres halmazt jelent. Természetesen a 0 kivételével nem tudunk elérni célösszeget - oszlopszámot.

Az első oszlopban minden bejegyzésnek szerepelnie kell true. Mindig, triviálisan, eljuthatunk 0 célösszegig, függetlenül attól, hogy milyen elemekkel kell dolgoznunk.

4. lépés: Az asztal felépítése (a probléma lényege)

Az i. És a j . trueOszlopban lévő táblázat néhány bejegyzése (elérhető), ha az alábbi három feltétel egyike teljesül:

1. az i -1 sorban és a j oszlopban szereplő bejegyzés az true. Emlékezzünk vissza arra, amit a sorszám képvisel. Ezért, ha a jelenleg rendelkezésünkre álló elemek egy részhalmazával el tudunk érni egy adott összeget, akkor azt az aktuális elemkészletünkkel is elérhetjük - egyszerűen nem használva az extra elemeket. Ez triviális. Nevezzük ezt prevRowIsTrue.
2. A jelenlegi elem pontosan az az összeg, amelyet el akarunk érni. Ez triviálisan is igaz. Nevezzük ezt isExactMatch.
3. Ha a fenti két feltétel nem teljesül, akkor a célösszeg elérésének egyetlen módja van. Itt használjuk az aktuális elemet - a jelenlegi sorunk elemkészletének kiegészítő elemét az előző sor elemkészletéhez képest -, és ellenőrizzük, hogy képesek vagyunk-e elérni a megcélzott összeg fennmaradó részét. Nevezzük ezt canArriveAtSum.

Csomagoljuk ki a 3. feltételt. Csak akkor használhatjuk az aktuális elemet, ha az kisebb, mint a célösszeg. Ha egyenlőek, akkor a 2. feltétel teljesül. Ha nagyobb, akkor nem tudjuk használni. Ezért az első lépés annak biztosítása, hogy az aktuális elem <célösszeg.

Az aktuális elem használatát követően megmarad a célösszeg fennmaradó része. Ezután a fenti sor megfelelő bejegyzésének ellenőrzésével ellenőrizzük, hogy ez elérhető-e.

A szokásos KP-hez hasonlóan mi is fokozatosan akarjuk alulról felfelé építeni a táblázatunkat. Az alapesetekkel kezdjük, amíg el nem érjük a végső megoldást.

5. lépés: A válasz visszaadása

Egyszerűen visszatérünk return mat[nums.length][totalSum / 2].

Működő kód

Köszönöm, hogy elolvasta!