streamalism.org

1. Bemutatkozás

A hátizsák probléma egy kombinatorikus optimalizálási probléma, amely sok alkalmazással rendelkezik. Ebben az oktatóanyagban megoldjuk ezt a problémát Java-ban.

2. A hátizsák probléma

A hátizsákproblémában van egy sor elemünk. Minden elemnek van súlya és értéke:

Ezeket a tárgyakat hátizsákba akarjuk tenni. Van azonban súlykorlátja:

Ezért olyan elemeket kell választanunk, amelyek össztömege nem haladja meg a súlyhatárt, és összértékük a lehető legmagasabb. Például a fenti példa legjobb megoldása az 5 kg-os és a 6 kg-os elem kiválasztása, amelyek maximális értéke 40 USD lehet a súlyhatáron belül.

A hátizsák problémának több változata van. Ebben az oktatóanyagban a 0-1 hátizsák problémára fogunk összpontosítani. A 0-1 hátizsákproblémában mindegyik elemet ki kell választani, vagy hátrahagyni. Részes mennyiséget nem vehetünk fel egy tételből. Emellett nem vehetünk fel többször egy elemet.

3. Matematikai meghatározás

Formalizáljuk most a 0-1 hátizsák problémát matematikai jelöléssel. Adott egy sor n tételek és a súlyhatár W, meghatározhatjuk az optimalizálási problémát:

Ez a probléma NP-nehéz. Ezért jelenleg nincs polinomiális idő algoritmus annak megoldására. Van azonban egy álpolinomiális idő algoritmus, amely dinamikus programozást használ erre a problémára.

4. Rekurzív megoldás

Rekurziós képletet használhatunk a probléma megoldására:

Ebben a képletben M (n, w) az optimális megoldás a n súlykorlátozású tételek w. Ez a következő két érték maximuma:

• Az optimális megoldás (n-1) súlykorlátozású tételek w (kivéve a n-edik tétel)
• A. Értéke n-adik tétel plusz az optimális megoldás innen (n-1) tételek és w mínusz súlya n-adik tétel (beleértve a n-edik tétel)

Ha a súlya n-th elem meghaladja az aktuális súlyhatárt, nem vesszük bele. Ezért a fenti két eset első kategóriájába tartozik.

Meg tudjuk valósítani ezt a rekurziós képletet Java-ban:

int hátizsákRec (int [] w, int [] v, int n, int W) {if (n W) {visszatérési hátizsákRec (w, v, n - 1, W); } else {return Math.max (hátizsákRec (w, v, n - 1, W), v [n - 1] + hátizsákRec (w, v, n - 1, W - w [n - 1]); }} 

Minden rekurziós lépésben két optimálisnál alacsonyabb megoldást kell értékelnünk. Ezért ennek a rekurzív megoldásnak a futási ideje: O (2n).

5. Dinamikus programozási megoldás

A dinamikus programozás stratégia az egyébként exponenciálisan nehéz programozási problémák linearizálására. Az ötlet az, hogy az alproblémák eredményeit tároljuk, hogy később ne kelljen újra kiszámítanunk őket.

A 0-1 hátizsák problémát dinamikus programozással is megoldhatjuk. A dinamikus programozás használatához először létrehozunk egy 2-dimenziós táblázatot, amelynek méretei 0 és n és 0-ig W. Ezután alulról felfelé irányuló megközelítést alkalmazunk az optimális megoldás kiszámításához ezzel a táblázattal:

int hátizsákDP (int [] w, int [] v, int n, int W) {if (n <= 0 || W <= 0) {visszatér 0; } int [] [] m = új int [n + 1] [W + 1]; mert (int j = 0; j <= W; j ++) {m [0] [j] = 0; } for (int i = 1; i <= n; i ++) {for (int j = 1; j j) {m [i] [j] = m [i - 1] [j]; } else {m [i] [j] = Math.max (m [i - 1] [j], m [i - 1] [j - w [i - 1]] + v [i - 1]); }}} visszatér m [n] [W]; } 

Ebben a megoldásban beágyazott hurok van az elemszám felett n és a súlyhatár W. Ezért ez a futási idő O (nW).

6. Következtetés

Ebben az oktatóanyagban megmutattuk a 0-1 hátizsák probléma matematikai definícióját. Ezután rekurzív megoldást adtunk erre a problémára a Java megvalósításával. Végül dinamikus programozást használtunk a probléma megoldására.

Mint mindig, a cikk forráskódja elérhető a GitHubon.