DAA – 0-1 Hátizsák

hirdetések

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.,

Reklámok

Leave a Comment