Frissítés: Olvassa el optimalizálja a tér komplexitás a dinamikus programozási megoldást, a follow-up cikk itt.,
a hátizsák probléma egy nagyon érdekes probléma kombinatorika-idézni Wikipedia,
” adott egy sor elem, mindegyik egy súly és egy érték, határozza meg az egyes elemek száma, hogy tartalmazza a gyűjtemény úgy, hogy a teljes súly kisebb vagy egyenlő egy adott határ, és a teljes érték a lehető legnagyobb.”
A Wikipédiából látjuk, hogy a hátizsák problémájának néhány változata létezik: 0-1 hátizsák, korlátozott hátizsák, korlátlan hátizsák., Ma a leggyakoribb (és legegyszerűbb) variációra koncentrálunk: a 0-1-es hátizsákos problémára.
a 0-1 hátizsák problémájának kissé érdekesebb és relatívabb megfogalmazása:
fontolja meg, hogy egy tolvaj betörjön egy házba, hogy kiraboljon,és hátizsákot hordoz. Vannak fix tételek száma az otthoni-mindegyik saját súlya és értéke-ékszerek, kisebb súly és a legmagasabb érték vs asztalok, kevesebb értéket, de sokkal nehéz. Üzemanyag hozzáadása a tűzhöz, a tolvajnak van egy régi hátizsákja, amely korlátozott kapacitással rendelkezik., Nyilvánvaló, hogy nem tudja felosztani az asztalt felére vagy ékszerekre 3/4th-re. Vagy elveszi, vagy elhagyja. Forrás
sajnos nehézségeim voltak a Hackerearth cikk egyes részeinek megértésében, ezért úgy döntöttem, hogy saját cikket írok. Ez a cikk nagyrészt a Hackerearth cikkén alapul, a kódrészleteket Java nyelven írják. További magyarázatokkal és részletekkel fogok foglalkozni, ahol szükségesnek érzem őket.
ezt a problémát dinamikus programozással fogjuk megoldani., A dinamikus programozás optimális alapszerkezetet és átfedő alproblémákat igényel, mindkettő jelen van a 0-1 hátizsák problémában, amint látni fogjuk.
rendben van, ha nem érti, hogy mi az “optimális alépítmény” és az “átfedő alproblémák” (ez egy cikk egy másik napra). Lényegében ez csak olyan problémák sajátos ízét jelenti, amelyek lehetővé teszik számunkra, hogy a korábbi megoldásokat kisebb problémákra újra felhasználjuk a jelenlegi probléma megoldásának kiszámításához. Majd meglátod, mire gondolok.,
Probléma részletek
Mivel ez a 0-1, hátizsák probléma, mi sem tartalmaz egy elemet a hátizsákot, vagy kizárják, de nem tartalmazzák a töredéke, vagy közé, többször is.
megoldás
először létrehozunk egy 2 dimenziós tömböt (azaz egy táblázatot) a n + 1 sorok és w + 1 oszlopok.
az I sorszám az 1— i Sor összes elemének halmazát jelöli. például a 3. sorban szereplő értékek azt feltételezik, hogy csak 1, 2 és 3 elemünk van.
A J oszlop a hátizsákunk tömegkapacitását jelöli., Ezért az 5. oszlopban szereplő értékek például azt feltételezik, hogy hátizsákunk 5 súlyegységet tartalmazhat.
mindent összerakva, egy bejegyzés az I sorban, a J oszlop a maximális értéket képviseli, amelyet az 1, 2, 3 … i tételekkel lehet elérni, egy hátizsákban, amely j súlyegységeket képes tartani.
hívjuk táblázatunkat mat a mátrixhoz. Ezért int mat = new int.
2. lépés:
azonnal elkezdhetjük kitölteni néhány bejegyzést a táblázatunkban: az alapesetek, amelyekre a megoldás triviális., Például a 0. sorban, ha nincs elemünk, akkor a hátizsákban tárolható maximális értéknek 0-nak kell lennie. Hasonlóképpen, a 0. oszlopban egy 0 tömegegységeket tartalmazó hátizsák esetében a benne tárolható maximális érték 0. (Feltételezzük, hogy nincsenek tömeg nélküli, értékes tárgyak.)
ezt megtehetjük 2 hurok:
3. Lépés (a probléma gyökere):
Most, hogy akarom kezdeni kitöltése a tábla., Mint minden dinamikus programozási megoldásnál, minden lépésben felhasználjuk a korábbi alproblémákra vonatkozó megoldásainkat.
először leírom a logikát, mielőtt konkrét példát mutatnék.
az I. sor, a J. oszlop és az előző alproblémák értékei közötti kapcsolat a következő:
emlékezzünk arra, hogy az I. és a J. oszlopban egy 1., 2., 3. tételekből álló alproblémát kezelünk j kapacitással. Jelenleg 2 lehetőségek ezen a ponton: mi sem tartalmazza elem i vagy sem., Ezért össze kell hasonlítanunk azt a maximális értéket, amelyet i.
tétel nélkül szerezhetünk meg. i. Sor, J. oszlop. ez a rész egyszerű. Az indoklás egyszerű: bármi maximális értéket megkapjuk a tételek 1, 2, 3 … azt kell, hogy nyilvánvalóan ugyanaz a maximális értéket megkapjuk a tételek 1, 2, 3 …, i – 1, ha úgy döntünk, hogy nem tartalmazza elem.
számítani a maximális értéket, hogy meg tudjuk szerezni a tétel én, először meg kell összehasonlítani a súlya elem a hátizsák súlya kapacitás., Nyilvánvaló, hogy ha a tétel súlya több, mint amit a hátizsák tud tartani, nem tudjuk felvenni, így nincs értelme elvégezni a számítást. Ebben az esetben a probléma megoldása egyszerűen a maximális érték, amelyet I. elem nélkül szerezhetünk be (azaz a fenti sorban lévő érték ugyanabban az oszlopban).
azonban tegyük fel, hogy az elem súlya kisebb, mint a hátizsák kapacitása. Így lehetőségünk van arra, hogy belefoglaljuk, ha potenciálisan növeli a maximálisan megszerezhető értéket., A maximális megszerezhető érték az I. tétel beillesztésével tehát = maga az I. elem értéke + a hátizsák fennmaradó kapacitásával elérhető maximális érték. Nyilvánvalóan teljes mértékben ki akarjuk használni hátizsákunk kapacitását, és nem hagyjuk, hogy a fennmaradó kapacitás hulladékká váljon.
ezért az I. sorban és a J. oszlopban (amely az ott elérhető maximális értéket képviseli) vagy azt a maximális értéket választanánk, amelyet I. elem nélkül szerezhetünk meg, vagy azt a maximális értéket, amelyet az I. tételhez szerezhetünk, amelyik nagyobb.
itt van egy konkrét példa arra, hogy mire gondolok.,
a 3.sorban (2. tétel), valamint az 5. oszlopban (4. hátizsák kapacitása) választhatjuk a 2. elemet (amely súlya 4 egység), vagy sem. Ha úgy döntünk, hogy nem vesszük fel, akkor a maximális érték, amelyet megszerezhetünk, megegyezik azzal, ha csak az 1.tétel közül választhatunk (amely a fenti sorban található, azaz 0)., Ha be akarjuk vonni a 2. tételt, akkor a 2. tételnél elérhető maximális érték a 2. elem (40) értéke + a maximális érték, amelyet a fennmaradó kapacitással szerezhetünk be(ami 0, mert a hátizsák már teljesen tele van).
a 3. sorban( 2. tétel) és a 10. oszlopban (9-es hátizsákkapacitás)ismét választhatjuk a 2. elemet, vagy sem. Ha úgy döntünk, hogy nem, akkor a maximális érték, amelyet megszerezhetünk, ugyanaz, mint a fenti sorban ugyanabban az oszlopban, azaz 10 (csak az 1.elemet, amelynek értéke 10). Ha a 2. tételt is tartalmazza, akkor a fennmaradó hátizsák kapacitása 9 – 4 = 5., Meg tudjuk találni a maximális értéket, amelyet 5-ös kapacitással lehet elérni a fenti sorban, az 5.oszlopban. Így a maximális érték, amelyet a 2. tétel beillesztésével szerezhetünk, 40 (a 2. tétel értéke) + 10 = 50.
az 50 vs 10 nagyobbat választjuk, így a maximális érték, amelyet az 1. és 2. tételekkel szerezhetünk be, 9-es hátizsák kapacitással, 50.,
Az algoritmus lehet kifejezni a Java, mint ez:
4. Lépés (végső megoldás):
Ha a táblázat óta lakott, a végső megoldás, az utolsó sorban az utolsó oszlopban, ami pedig a maximális érték megszerezhető a elemek, valamint a teljes kapacitását a hátizsákot.
return mat;
munkakód:
megjegyzés: itt nyomtattam a végső választ a visszaküldés helyett, mivel minden a nyilvános statikus üresség fő alatt van elhelyezve.,
Thanks for reading!