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 + 1
sorokat 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 + 1
oszlopokat 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 . true
Oszlopban lévő táblázat néhány bejegyzése (elérhető), ha az alábbi három feltétel egyike teljesül:
- 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 eztprevRowIsTrue
. - A jelenlegi elem pontosan az az összeg, amelyet el akarunk érni. Ez triviálisan is igaz. Nevezzük ezt
isExactMatch
. - 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!