Fraktioneret rygsæk i lineær tid

Det ville være rart, hvis du sagde problemet. Jeg antager, at du har $ n $ poster $ x_i $ , der hver har overskud $ p_i $ og vægt $ w_i $ . Du vil maksimere din fortjeneste under den begrænsning, at den samlede vægt højst er $ W $ . For hvert element $ x_i $ har du lov til at sætte en hvilken som helst brøkdel $ \ theta \ i [0,1] $ af det, hvilket giver dig fortjeneste $ \ theta p_i $ og vægt $ \ theta w_i $ .

Her er et eksempel. Du har rå guld med et overskud på $ 1000 $ og vægt $ 1 $ . Du har også bananer med et overskud på $ 1 $ og vægt $ 10 $ . Antag at du kan bære en vægt på $ 2 $ . Hvad ville du gøre? Naturligvis vil du først lægge så meget guld som du kan – nemlig det hele, og derefter lægge det så mange bananer som du kan – nemlig en tiendedel af det til en samlet fortjeneste på $ 1000,1 $ .

Den generelle algoritme er ens. Antag at du deler $ W $ i en $ 1000 $ “slots”, som du vil udfylde mest rentable emnedele af vægt $ W / 1000 $ . For en vare, der vejer $ w_i $ , har vi $ w_i / (W / 1000) $ stykker (antag i det øjeblik, at dette er et heltal), og hver af dem er værd $ p_i / (w_i / (W / 1000)) $ . Når vi vælger, hvad vi skal sætte i en slot, vil vi gerne maksimere vores overskud, og derfor vælger vi varen med maksimal $ p_i / w_i $ , og sætter den så mange stykker som muligt. Hvis vi løber tør, vælger vi elementet med den næststørste $ p_i / w_i $ og så videre.

Du kan implementere dette uden at dele $ W $ i en $ 1000 $ stykker: Vælg emnet med maksimal $ p_i / w_i $ , og læg så meget af det som muligt. Hvis du løber tør, skal du vælge den næste og lægge så meget af det som muligt. Og så videre. Implementering af denne algoritme kræver sortering af listen $ p_i / w_i $ , hvilket tager tid $ O (n \ log n) $ . Algoritmen, du beskriver, bruger det samme trick-brug i hurtigvalg til at reducere kørselstiden til $ O (n) $ , på bekostning af at algoritmen bliver randomiseret.

Jeg foreslår følgende rute for at forstå algoritmen:

1. Forstå den klassiske grådige algoritme for fraktioneret rygsæk.
2. Forstå hurtigvalg.
3. Se hvordan den algoritme, du citerer, kombinerer quickselect-teknikken med den grådige tilgang.

R er sættet med forholdet mellem fortjeneste / vægt for hvert objekt , hvor fortjeneste og vægt af objekter er givet. Og W er kapaciteten for rygsæk .
Nu i stedet for at vælge tilfældigt element i 1-trins kan vi anvende medianfindingsalgoritme til find medianen i O (n) gange.
Og så kan vi gøre resten af alle trin.Så tidskompleksitetsanalysen vil være –
        T (n) = T (n / 2) + O (n).
Og vi får O (n) som løsning. Fortæl mig, om noget ikke er korrekt forklaret, og du vil vide noget mere.

På lineær tid kan du finde median vare udtrykt i værdi pr. vægtenhed. Derefter, også i lineær tid, kan du finde ud af, om du kan passe alle genstande, der mindst er så værdifulde i rygsækken eller ej. Hvis du kan, skal du gøre det og løse dette problem rekursivt for n / 2 emner af lavere værdi, forudsat at du ” har allerede fyldt rygsækken. Hvis du ikke kan “t, kan du smide n / 2 emner af lavere værdi, og prøv derefter at løse problemet igen med kun n / 2 emner af højeste værdi.

Gentagelsen her er T (n) = T (n / 2) + O (n) , og vi har det T (n) = O (n) efter ønske.

I den løsning, du har indsat: R er sættet med forhold, fortjeneste / vægt W er opsummeringen af hele vægten af dette sæt , bruges til at sammenligne med kapaciteten på din rygsæk. Tilsvarende repræsenterer {pi / wi | pi / wi} det iith-element fortjeneste er til ith vægtværdien. Vi sammenligner denne værdi med den tilfældigt valgte r -værdi og adskiller os derefter baseret på sammenligningen af forholdet. R1, R2, R3 er yderligere undergrupper af det indstillede forhold afhængigt af forholdet, der er mindre, lige eller større end for det mediale element.

Tilsvarende er W1, W2, W3 summeringen af vægten af disse sæt.

Vælg nu det passende løsningssæt afhængigt af forholdsværdierne som beskrevet i starten.