Törött hátizsák lineáris időben

Jó lenne, ha kijelennéd a problémát. Feltételezem, hogy van $ n $ elem $ x_i $ , amelyek mindegyike profit $ p_i $ és súly $ w_i $ . Maximalizálni szeretné nyereségét azzal a megkötéssel, hogy az össztömeg legfeljebb $ W $ . Minden egyes elemre $ x_i $ megengedett, hogy a $ \ theta \ bármely törtjét a [0,1] $ , amivel profitot nyer $ \ theta p_i $ és súlyt $ \ theta w_i $ .

Íme egy példa. Nyers aranyad van, nyeresége 1000 $ és súlya 1 $ . Van banánja is, amelynek haszna $ 1 $ és súlya $ 10 $ . Tegyük fel, hogy hordozhat $ 2 $ súlyt. Mit csinálnál? Természetesen először annyi aranyat teszel, amennyit csak tudsz – mégpedig az egészet, és akkor annyi banánt teszel, amennyit csak tudsz – mégpedig egy tizedét, a $ 1000.1 $ .

Az általános algoritmus hasonló. Tegyük fel, hogy felosztja a $ W $ -ot egy 1000 $ $ “résszel”, amelyet a legjobban szeretne kitölteni nyereséges súlyrész $ W / 1000 $ . $ w_i $ súlyú tétel esetén $ w_i / (W / 1000) $ darab van (tegyük fel, hogy abban a pillanatban, hogy ez egy egész szám), és mindegyikük megéri $ p_i / (w_i / (W / 1000)) $ . Amikor kiválasztjuk, mit tegyünk egy résbe, szeretnénk maximalizálni a nyereségünket, ezért a maximális $ p_i / w_i $ elemet választjuk, és annyit tegyünk darabokat. Ha elfogy, akkor a következő legnagyobb $ p_i / w_i $ stb. Elemet választjuk.

Ezt felosztás nélkül is megvalósíthatja. $ W $ 1000 $ $ darabokra: Válassza ki a maximális $ p_i / w_i $ , és tegye belőle a lehető legtöbbet. Ha elfogy, válassza a következőt, és tegye belőle a lehető legtöbbet. Stb. Az algoritmus megvalósításához meg kell rendezni a $ p_i / w_i $ listát, amely időbe telik $ O (n \ log n) $ . Az általad leírt algoritmus ugyanazt a trükköt használja a quickselect alkalmazásban, hogy csökkentse a futási időt $ O (n) $ -ra, az algoritmus véletlenszerűvé tételének árán.

A következő útvonalat javaslom az algoritmus megértéséhez:

1. Ismerje meg a töredékes hátizsák klasszikus mohó algoritmusát.
2. A quickelect megértése.
3. Nézze meg, hogyan ötvözi az idézett algoritmus a quickselect technikáját a kapzsi megközelítéssel.

R a minden tárgy nyereség / tömeg arányaránya , ahol megadják a tárgyak nyereségét és súlyát. És W a hátizsák kapacitása .
Most ahelyett, hogy 1 lépésben véletlenszerű elemet választanánk, alkalmazhatunk medián keresési algoritmust a medián megtalálása O (n) alkalommal.
És akkor megtehetjük az összes lépést.Tehát az idő bonyolultság-elemzése a következő lesz:
        T (n) = T (n / 2) + O (n).
És O (n) -et kapunk megoldásként. Mondja meg, ha valami nincs megfelelően megmagyarázva, és szeretne még valamit tudni.

Lineáris időben megtalálja a medián tétel az egységnyi tömegre vonatkoztatott értékben. Ezután lineáris időben is kitalálhatja, hogy elfér-e minden olyan elem, amely legalább annyira értékes a hátizsákban, vagy sem. Ha teheti, akkor tegye meg, és rekurzív módon oldja meg ezt a problémát az n / 2 alacsonyabb értékű tételeknél, ha Ön ” Már megtöltötte a hátizsákot. Ha nem tudja, akkor kidobhatja az alacsonyabb értékű n / 2 elemeket, majd próbálja meg újra megoldani a problémát csak a n / 2 elemekkel, amelyek a legnagyobb értéket képviselik.

Itt a megismétlődés T (n) = T (n / 2) + O (n) , és ez megvan T (n) = O (n) , igény szerint.

A beillesztett megoldásban: R a arányok halmaza, nyereség / súly W a halmaz teljes súlyának összegzése , összehasonlítva a hátizsákod kapacitásával. Hasonlóképpen, a {pi / wi | pi / wi} az i-edik elemeket jelenti a nyereség és az i-edik tömegérték között. Összehasonlítjuk ezt az értéket a véletlenszerűen kiválasztott r értékkel, majd az arány összehasonlítása alapján elkülönítjük. Az R1, R2, R3 további arányai a beállított aránynak, attól függően, hogy az arány kisebb, egyenlő vagy nagyobb, mint a a medián elem.

hasonlóképpen a W1, W2, W3 ezeknek a halmazoknak a súlya összegezve.

Most válassza ki a megfelelő megoldáskészletet az arányértékektől függően, ahogyan azt a kezdetnél kifejtettük.