korábban már tárgyalt frakcionált Hátizsák probléma segítségével mohó megközelítés. Megmutattuk, hogy a mohó megközelítés optimális megoldást nyújt a frakcionált hátizsákhoz. Ez a fejezet azonban a 0-1.
0-1 hátizsákban az elemeket nem lehet megtörni, ami azt jelenti, hogy a tolvajnak az elemet egészében kell vennie, vagy el kell hagynia., Ez az oka annak, hogy 0-1 hátizsáknak hívják.
ezért 0-1 Hátizsák esetén a xi értéke lehet 0 vagy 1, ahol más korlátok ugyanazok maradnak.
0-1 Knapsack nem oldható meg mohó megközelítéssel. A mohó megközelítés nem biztosítja az optimális megoldást. Sok esetben a mohó megközelítés optimális megoldást jelenthet.
a következő példák határozzák meg nyilatkozatunkat.
példa-1
vegyük figyelembe, hogy a hátizsák kapacitása W = 25, az elemek pedig az alábbi táblázatban láthatók.,
| Elem | Egy | B | C | D |
|---|---|---|---|---|
| Profit | 24 | 18 | 18 | 10 |
| > Tömege | 24 | 10 | 10 | 7 |
Anélkül, hogy figyelembe véve a profit egységnyi tömeg (pi/wi), ha alkalmazni, Kapzsi megközelítés, hogy megoldja ezt a problémát, az első elem lesz a kiválasztott, mivel hozzájárul a maximális profit között az elemek.,
az A Elem kiválasztása után nem lesz több elem kiválasztva. Ezért az adott tételkészlet teljes nyeresége 24. Míg az optimális megoldás a B és C elemek kiválasztásával érhető el, ahol a teljes nyereség 18 + 18 = 36.
példa-2
az elemek kiválasztása helyett a teljes előny alapján ebben a példában az elemek a PI/wi arány alapján kerülnek kiválasztásra. Vegyük figyelembe, hogy a hátizsák kapacitása W = 60, a tételek pedig az alábbi táblázatban láthatók.,
| Item | A | B | C |
|---|---|---|---|
| Price | 100 | 280 | 120 |
| Weight | 10 | 40 | 20 |
| Ratio | 10 | 7 | 6 |
Using the Greedy approach, first item A is selected. Then, the next item B is chosen. Hence, the total profit is 100 + 280 = 380., Ennek a példánynak az optimális megoldása azonban a B és C elemek kiválasztásával érhető el, ahol a teljes nyereség 280 + 120 = 400.
ezért arra lehet következtetni, hogy a mohó megközelítés nem adhat optimális megoldást.
a 0-1 Hátizsák megoldásához dinamikus programozási megközelítésre van szükség.
Problem Statement
egy tolvaj kirabol egy boltot, és maximális W-S súlyt tud cipelni a hátizsákjába. Vannak n tételek súlya ith elem wi, a nyereség kiválasztása ez a tétel pi. Milyen elemeket kell a tolvajnak venni?,
Dynamic-Programming Approach
let I be the highest-numbered elem in an optimal solution S for W dollars. Ezután az S ‘ = S – {I} optimális megoldás a W-wi dollárhoz, az S megoldás értéke pedig Vi plusz az alprobléma értéke.
ezt a tényt a következő képletben fejezhetjük ki: határozzuk meg, hogy a C legyen a megoldás az 1,2,…, i és a maximális súly w.,
Az algoritmus kerül a következő bemenetek
-
A maximális súly W
-
A tételek száma n
-
A két szekvencia v = <v1, v2, …, vn>, majd a w = <w1, w2, …, wn>
A készlet elemeket, hogy lehet következtetni, hogy az asztalra, kezdve a c követése visszafelé, ahol az optimális értékek jött.
Analysis
Ez az algoritmus θ(n, w) időt vesz igénybe, mint a C táblázat (n + 1).(w + 1) bejegyzések, ahol minden bejegyzéshez θ(1) idő szükséges a számításhoz.,