Murto-reppu lineaarisessa ajassa

Olisi mukavaa, jos ilmoittaisit ongelman. Oletan, että sinulla on $ n $ kohdetta $ x_i $ , joista jokaisella on voittoa $ p_i $ ja paino $ w_i $ . Haluat maksimoida voittosi sillä ehdolla, että kokonaispaino on enintään $ W $ . Kullekin nimikkeelle $ x_i $ voit laittaa minkä tahansa murto-osan $ \ theta \ kohtaan [0,1] $ , mikä antaa sinulle voittoa $ \ theta p_i $ ja paino $ \ theta w_i $ .

Tässä on esimerkki. Sinulla on raakakultaa, jonka voitto on 1000 $ ja paino 1 $ . Sinulla on myös banaaneja, joiden voitto on $ 1 $ ja paino 10 $ $ . Oletetaan, että voit kantaa painoa $ 2 $ . Mitä sinä tekisit? Luonnollisesti laitat ensin niin paljon kultaa kuin voit – nimittäin kaiken sen, ja sitten laitat sen niin monta banaania kuin pystyt – nimittäin kymmenesosa siitä, saadaksesi $ 1000.1 $ .

Yleinen algoritmi on samanlainen. Oletetaan, että jaat $ W $ 1000 $ $ ”paikkoihin”, jotka haluat täyttää eniten kannattavat paino-osuudet $ W / 1000 $ . Tuotteelle, joka painaa $ w_i $ , meillä on $ w_i / (W / 1000) $ kappaletta (oletetaan sillä hetkellä, kun tämä on kokonaisluku), ja kukin niistä on arvo $ p_i / (w_i / (W / 1000)) $ . Kun valitsemme, mitä paikkaan laitetaan, haluaisimme maksimoida voittomme, joten valitsemme kohteen, jonka $ p_i / w_i $ , ja laitamme sen niin moneksi paloja kuin mahdollista. Jos loppumme, valitsemme kohteen, jolla on seuraavaksi suurin $ p_i / w_i $ ja niin edelleen.

Voit toteuttaa tämän jakamatta $ W $ $ 1000 $ kappaleena: Valitse kohde, jossa on enintään $ p_i / w_i $ ja aseta se niin paljon kuin mahdollista. Jos loppuu, valitse seuraava ja aseta se niin paljon kuin mahdollista. Ja niin edelleen. Tämän algoritmin käyttöönotto edellyttää luettelon $ p_i / w_i $ lajittelua, mikä vie aikaa $ O (n \ log n) $ . Kuvaamasi algoritmi käyttää samaa temppukäyttöä quickselectissä vähentämään ajoaikaa $ O (n) $ , kustannuksella, että algoritmi satunnaistetaan.

Ehdotan seuraavaa reittiä algoritmin ymmärtämiseksi:

1. Ymmärrä murto-repun klassinen ahne algoritmi.
2. Ymmärrä pikavalinta.
3. Katso, kuinka lainaamasi algoritmi yhdistää pikavalintatekniikan ahneeseen lähestymistapaan.

R on jokaisen kohteen voiton / painon suhdejoukko , jossa annetaan voitto ja esineiden paino. Ja W on repun kapasiteetti .
Nyt sen sijaan, että valitsisimme satunnaisen elementin 1-vaiheessa, voimme käyttää mediaanihakualgoritmia etsi mediaani O (n) kertaa.
Ja sitten voimme tehdä loput kaikista vaiheista.Joten ajan monimutkaisuusanalyysi on –
        T (n) = T (n / 2) + O (n).
Ja saamme ratkaisuksi O (n) . Kerro minulle, jos jotain ei ole selitetty oikein ja haluat tietää jotain enemmän.

Lineaarisessa ajassa löydät mediaaniarvo painoyksikköä kohti laskettuna. Sitten, myös lineaarisessa ajassa, voit selvittää, mahtuvatko kaikki tuotteet, jotka ovat ainakin arvokkaita repussa vai eivät. Jos voit, tee niin ja ratkaise tämä ongelma rekursiivisesti n / 2 -kohteille, joiden arvo on pienempi, Olemme jo täyttäneet repun. Jos et voi, niin voit heittää pienemmän arvon n / 2 -esineet pois, ja yritä sitten ratkaista ongelma uudelleen vain korkeimpien n / 2 -kohteiden kanssa.

Tässä toistuminen on T (n) = T (n / 2) + O (n) , ja meillä on se, että T (n) = O (n) , haluamallasi tavalla.

Liittämässäsi ratkaisussa: R on joukkojen suhde, voitto / paino W on tämän sarjan koko painon summa , käytetään vertaamaan reppusi kapasiteettiin. Vastaavasti {pi / wi | pi / wi} edustaa i: n elementin voittoa i: n painon arvoon. Vertailemme tätä arvoa satunnaisesti valittuun r -arvoon ja sitten erotetaan suhdeluvun perusteella. R1, R2, R3 ovat muita asetetun suhteen osajoukkoja riippuen siitä, onko suhde pienempi, yhtä suuri tai suurempi kuin mediaanielementti.

vastaavasti W1, W2, W3 ovat näiden joukkojen painojen summa.

Valitse nyt sopiva ratkaisujoukko suhteiden arvojen mukaan, kuten alussa selitetään.