Fraktionerad ryggsäck i linjär tid

Det skulle vara trevligt om du uppgav problemet. Jag antar att du har $ n $ objekt $ x_i $ , var och en har vinst $ p_i $ och vikt $ w_i $ . Du vill maximera din vinst under begränsningen att den totala vikten är högst $ W $ . För varje objekt $ x_i $ har du rätt att placera alla fraktioner $ \ theta \ i [0,1] $ av det, vilket ger dig vinst $ \ theta p_i $ och vikt $ \ theta w_i $ .

Här är ett exempel. Du har råguld med en vinst på $ 1000 $ och vikt $ 1 $ . Du har också bananer med en vinst på $ 1 $ och vikt $ 10 $ . Antag att du kan bära vikten $ 2 $ . Vad skulle du göra? Naturligtvis skulle du först lägga så mycket guld du kan – nämligen allt, och sedan skulle du lägga det så många bananer som du kan – nämligen en tiondel av det, för en total vinst på $ 1000,1 $ .

Den allmänna algoritmen liknar. Antag att du delar upp $ W $ i en $ 1000 $ ”slots”, som du vill fylla med mest lönsamma viktdelar $ W / 1000 $ . För en artikel som väger $ w_i $ har vi $ w_i / (W / 1000) $ bitar (antag för tillfället att detta är ett heltal), och var och en av dem är värda $ p_i / (w_i / (W / 1000)) $ . När vi väljer vad vi ska lägga i en kortplats vill vi maximera vår vinst, och därför väljer vi objektet med maximal $ p_i / w_i $ och lägger det så många bitar som möjligt. Om vi tar slut väljer vi objektet med näst största $ p_i / w_i $ och så vidare.

Du kan implementera detta utan att dela $ W $ i en $ 1000 $ -stycken: Välj artikel med maximal $ p_i / w_i $ , och lägg så mycket av det som möjligt. Om du tar slut väljer du nästa och lägger så mycket av det som möjligt. Och så vidare. Att implementera denna algoritm kräver att du sorterar listan $ p_i / w_i $ , vilket tar tid $ O (n \ log n) $ . Algoritmen som du beskriver använder samma trickanvändning i snabbval för att minska körtiden till $ O (n) $ , till kostnad för att göra algoritmen slumpmässig.

Jag föreslår följande väg för att förstå algoritmen:

1. Förstå den klassiska giriga algoritmen för fraktionerad ryggsäck.
2. Förstå snabbval.
3. Se hur algoritmen du citerar kombinerar quickselect-tekniken med den giriga metoden.

R är uppsättningen av förhållandet mellan vinst / vikt för varje objekt , där vinst och vikt för objekt ges. Och W är kapaciteten för ryggsäck .
Nu istället för att välja slumpmässigt element i ett steg kan vi tillämpa algoritm för medianfynd på hitta median i O (n) gånger.
Och då kan vi göra resten av alla steg.Så tidskomplexitetsanalysen blir –
        T (n) = T (n / 2) + O (n).
Och vi får O (n) som lösning. Berätta för mig om något inte förklaras ordentligt och du vill veta något mer.

På linjär tid kan du hitta medianvärdet uttryckt i värde per viktenhet. Sedan, även linjärt, kan du ta reda på om du kan passa alla föremål som är minst så värdefulla i ryggsäcken eller inte. Om du kan, gör det och lösa problemet rekursivt för n / 2 artiklar med lägre värde med tanke på att du ” har redan fyllt ryggsäcken. Om du inte kan ”t, kan du slänga n / 2 lägre värde, och försök sedan lösa problemet igen med endast n / 2 objekt med högsta värde.

Återkomsten här är T (n) = T (n / 2) + O (n) , och vi har det T (n) = O (n) , efter önskemål.

I den lösning du har klistrat in: R är uppsättningen förhållanden, vinst / vikt W är summeringen av hela vikten för denna uppsättning , används för att jämföra med kapaciteten på din ryggsäck. På samma sätt representerar {pi / wi | pi / wi} det ith-elementets vinst är till det ith viktvärdet. Vi jämför detta värde med det slumpmässigt valda r -värdet och segregerar sedan baserat på jämförelsen av förhållandet. R1, R2, R3 är ytterligare underuppsättningar av det inställda förhållandet beroende på att förhållandet är mindre, lika eller större än för medianelementet.

På samma sätt är W1, W2, W3 summeringen av vikterna i dessa uppsättningar.

Välj nu lämplig lösningsuppsättning beroende på förhållandevärdena som förklaras vid start.