A hátizsák-probléma egy változata: hogyan oldható meg a Partition Equal Subset Sum probléma Java-ban

Frissítés: A dinamikus programozási megoldás térbonyolultságának optimalizálásáról itt olvashat további cikkemben.

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

Ma szeretnék megvitatni a KP egyik változatát: a partíció egyenlő részhalmaz összegének problémája. Először láttam ezt a problémát a Leetcode-on - ez ösztönözte nekem a KP-ről való ismeretemet, és arról, hogy írjak róla.

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

Adjon meg egy nem üres tömböt, amely csak pozitív egész számokat tartalmaz, keresse meg, lehet-e a tömb két részhalmazra bontani úgy, hogy mindkét részhalmazban az elemek összege egyenlő legyen.

A probléma teljes megállapításához, korlátozásokkal és példákkal, nézze meg a Leetcode problémát.

Dinamikus programozás

A KP-hez hasonlóan ezt dinamikus programozással is megoldjuk. Mivel ez a KP variációja, a logika és a módszertan nagyjából hasonló.

Megoldás

Megoldásunkat olyan módszerrel fogjuk beépíteni, amely visszaadja a logikai értékeket - igaz, ha a tömb egyenlő részhalmazokra osztható, máskülönben hamis.

1. lépés: Óvás a páratlan tömbösszeg ellen

Triviálisan, ha a tömb összes számának összege páratlan, akkor hamis értéket adhatunk vissza. Csak akkor folytatjuk, ha a tömb egyenletes összeget eredményez.

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

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

A táblázatsorok a figyelembe veendő tömb elemek halmazát képviselik, míg a táblázati oszlopok azt az összeget jelzik, amelyre meg akarjuk érni. A táblázat értékei egyszerűen logikai értékek, jelezve, hogy egy összeg (oszlop) megszerezhető-e tömb elemek halmazával (sor).

Konkrétan az i sor a 0 és (i-1) indexek közötti tömb elemek halmazát képviseli. Az 1 eltolás oka az, hogy a 0. sor üres elemekből áll. Ezért az 1. sor az első tömb elemet jelzi (0. index), a 2. sor az első két tömb elemet (0–1 indexek), és így tovább. Összességében n + 1 sort hozunk létre, 0-val együtt.

Csak azt akarjuk tudni, hogy pontosan össze tudjuk-e hozni a tömb teljes összegének felét. Tehát csak totalSum / 2 + 1 oszlopokat kell létrehoznunk, 0-val együtt.

3. lépés: Az asztal előtöltése

Azonnal megkezdhetjük a táblázatban az alapesetek bejegyzésének kitöltését - a 0. sor és a 0. oszlop.

Az első sorban minden bejegyzésnek hamisnak kell lennie - az első kivételével. Emlékezzünk arra, hogy az első sor üres halmazt jelent. Természetesen nem érhetünk el egyetlen célösszeget sem - oszlopszámot - kivéve a 0-t.

Az első oszlopban minden bejegyzésnek igaznak kell lennie. Mindig, triviálisan, elérhetjük a 0 célösszeget, függetlenül attól, hogy milyen elemekből állunk együtt.

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

Az i. Sorban és a j oszlopban szereplő táblázat néhány bejegyzése igaz (elérhető), ha a következő három feltétel valamelyike ​​teljesül:

  1. az i-1. sor és a j oszlop bejegyzése igaz. Emlékezzen arra, amit a sor száma képvisel. Ezért, ha képesek vagyunk bizonyos összeget elérni a jelenleg meglévő elemek egy részhalmazával, akkor ezt az összeget a jelenlegi elemkészletünkkel is elérhetjük - egyszerűen az extra elemek használata nélkül. Ez triviális. Hívjuk ezt a prevRowIsTrue-nak.
  2. A jelenlegi elem pontosan az az összeg, amelyet el akarunk érni. Ez szintén triviálisan igaz. Hívjuk ezt isExactMatch-nek.
  3. Ha a fenti két feltétel nem teljesül, akkor van még egy út a célösszeg eléréséhez. Itt az aktuális elemet használjuk - a kiegészítő elem az aktuális sor elemkészletében az előző sor elemkészletéhez képest -, és ellenőrizzük, hogy képesek-e elérni a célösszeg fennmaradó részét. Hívjuk ezt a canArriveAtSum néven.

Kicsomagoljuk a 3. feltételt. Csak akkor használhatjuk az aktuális elemet, ha kevesebb, mint a célösszeg. Ha egyenlők, akkor a 2. feltétel teljesül. Ha nagyobb, akkor nem használhatjuk fel. Ezért az első lépés annak biztosítása, hogy az aktuális elem

A jelenlegi elem felhasználása után megmarad a célösszeg fennmaradó része. Ezután megvizsgáljuk, hogy ez elérhető-e, a fenti sor megfelelő tételének ellenőrzésével.

A szokásos KP-hez hasonlóan, fokozatosan szeretnénk alulról felfelé építkezni az asztalunkra. Az alapesetekkel kezdjük, amíg meg nem találjuk a végső megoldást.

5. lépés: A válasz visszatérése

Egyszerűen visszaadjuk a visszatérő szőnyeget [nums.length] [totalSum / 2].

Működési kód

Köszönöm, hogy elolvasta!