A hátizsák probléma
a hátizsák probléma egyszerre trükkös és érdekes. Biztos vagyok benne, hogy ha meglátogatja ezt az oldalt, akkor már ismeri a probléma kijelentést, de csak a Befejezés kedvéért :
probléma:
mivel a W és N elemek maximális kapacitása van, mindegyik saját értékével és súlyával, dobja be az elemeket a hátizsákba úgy, hogy a végső tartalom maximális értékkel rendelkezzen. Juj !!,
itt van a probléma általános magyarázata – fontolja meg, hogy egy tolvaj otthonba kerül, hogy kiraboljon, és hátizsákot hordoz. Az otthonban fix számú tárgy található – mindegyik saját súlyával és értékével -, kisebb súlyú és legnagyobb értékű asztalokkal, kisebb értékekkel, de sokkal nehezebb. Ü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
példa :
Knapsack Max weight : W = 10 (units)Total items : N = 4Values of items : v = {10, 40, 30, 50}Weight of items : w = {5, 4, 6, 3}
a példaadatok áttekintő áttekintése azt mondja nekünk, hogy a maximális érték, amelyet a 10 maximális súlyával el tudunk fogadni, 50 + 40 = 90, súlya 7.
megközelítés:
az optimálisan megoldott módszer a dinamikus programozás – a kisebb csomagolási problémák megoldása, majd a nagyobb probléma bővítése.,
építsünk egy elemet X tömeg tömb nevű V (érték tömb):
V = 4 rows * 10 columnsAz egyes értékek ebben a mátrixban egy kisebb Hátizsák probléma.
alap eset 1 : vegyük a 0. oszlop esetét. Ez csak azt jelenti, hogy a hátizsáknak 0 kapacitása van. Mit tudsz bennük tartani? Semmi. Tehát töltsük fel őket 0S-vel.
2 alap eset: vegyük a 0 sor esetét. Ez csak azt jelenti, hogy nincsenek elemek a házban. Mit tart a hátizsákjában, ha nincsenek elemek. Már megint semmi !!! Minden nulla.,
megoldás:
1) most kezdjük el a tömb sorának kitöltését. Mit jelent az 1. sor és az 1. oszlop? Hogy mivel az első elem (sor), tudja befogadni azt a hátizsák kapacitása 1 (oszlop). Nem. Az első tétel súlya 5. Tehát töltsük be a 0-t. Valójában nem tudnánk kitölteni semmit, amíg el nem érjük az 5.oszlopot (5. Súly).
2) Miután elérjük az 5.oszlopot (ami 5. súlyt jelent) az első sorban, ez azt jelenti, hogy el tudjuk fogadni az 1. elemet., Töltsük 10 van (ne feledd, ez egy Érték tömb):
3) Mozgó, a súly 6 (oszlop 6) tudjuk befogadni mást, a maradék tömege 1 (súly – tömeg ez a tétel => 6 – 5). Hé, ne feledd, mi vagyunk az első tétel. Így, ez a fajta intuitív, hogy a többi sorban lesz csak ugyanaz az érték is, mivel nem tudjuk felvenni bármely más elem, hogy extra súlyt, hogy van.,
4) tehát a következő érdekes dolog történik, amikor elérjük a 4.oszlopot a harmadik sorban. A jelenlegi futási súly 4.
ellenőriznünk kell a következő eseteket.
1) tudunk befogadni tétel 2-Igen, tudjuk. A 2. tétel súlya 4.
2) az aktuális súly értéke magasabb a 2. tétel nélkül? – Ellenőrizze az előző sor azonos súlyú. Nem. az előző sorban * van 0 benne, mivel nem voltunk képesek befogadni tétel 1 súly 4.
3) tudunk befogadni két elem azonos súlyú, hogy tudtuk maximalizálni az értéket? – Nem., A fennmaradó súly a tétel levonása után2 súlya 0.
miért az előző sor?
egyszerűen azért, mert maga a 4. súlynál az előző sor egy kisebb hátizsákoldat, amely megadja a maximális értéket, amely addig a pontig felhalmozódhat (áthaladva az elemeken).,
példázza,
1) az aktuális elem értéke = 40
2) az aktuális elem súlya = 4
3) a fennmaradó súly = 4-4 = 0
4) Ellenőrizze a fenti sort (a fenti tétel az 1.tétel esetében vagy a halmozott Max érték a többi sor esetében). A fennmaradó Súly 0, képesek vagyunk befogadni tétel 1? Egyszerűen fogalmazva, van-e egyáltalán érték a fenti sorban az adott súlyra?,
a számítás így megy:
1) Vegye be az azonos súlyra vonatkozó maximális értéket e tétel nélkül:
previous row, same weight = 0=> V2)vegye be az aktuális elem értékét + érték, amelyet a fennmaradó tömeggel tudunk befogadni:
Max a kettő között 40 (0 és 40).
3) a következő és legfontosabb esemény a 9.és a 2. oszlopban történik. Ami azt jelenti, hogy 9-es súlyunk van, és két elemünk van. A példaadatokat tekintve az első két tételt el tudtuk fogadni., Itt néhány dolgot veszünk figyelembe:
- az aktuális elem értéke = 40
- az aktuális elem súlya = 4
- a fennmaradó súly = 9 – 4 = 5
- ellenőrizze a fenti sort. A fennmaradó súly 5, képesek vagyunk befogadni tétel 1.
Tehát a számítás :
1) a max érték ugyanaz a tömeg, anélkül, hogy ez a tétel:
previous row, same weight = 102) az értéke az aktuális elem + érték, hogy felhalmozódnak a maradék tömeg:
Value of current item (40)+ value in previous row with weight 5 (total weight until now (9) - weight of the current item (4))= 1010 vs 50 = 50.,
mindezen kisebb problémák megoldásának végén csak vissza kell adnunk az értéket a V-4. tételnél a 10. súlynál:
komplexitás
a megoldás összetettségének elemzése meglehetősen egyenes. Csak egy hurok van W-hez egy n => O (NW)
végrehajtás:
itt jön a kötelező végrehajtási kód Java-ban: