Brøkdel av ryggsekk i lineær tid

Det ville være fint om du uttalte problemet. Jeg antar at du har $ n $ elementer $ x_i $ , som hver har fortjeneste $ p_i $ og vekt $ w_i $ . Du vil maksimere fortjenesten under begrensningen at totalvekten maksimalt er $ W $ . For hvert element $ x_i $ har du lov til å sette en hvilken som helst brøkdel $ \ theta \ i [0,1] $ av den, noe som gir deg fortjeneste $ \ theta p_i $ og vekt $ \ theta w_i $ .

Her er et eksempel. Du har rå gull, med et overskudd på $ 1000 $ og vekt $ 1 $ . Du har også bananer med et overskudd på $ 1 $ og vekt $ 10 $ . Anta at du kan bære en vekt på $ 2 $ . Hva ville du gjort? Naturligvis vil du først sette så mye gull du kan – nemlig det hele, og så vil du sette det så mange bananer som du kan – nemlig en tidel av det, for en total fortjeneste på $ 1000,1 $ .

Den generelle algoritmen er lik. Anta at du deler $ W $ i en $ 1000 $ «slots», som du vil fylle ut med mest lønnsomme vektdeler $ W / 1000 $ . For en vare som veier $ w_i $ , har vi $ w_i / (W / 1000) $ stykker (antar for øyeblikket at dette er et heltall), og hver av dem er verdt $ p_i / (w_i / (W / 1000)) $ . Når vi velger hva vi skal plassere i et spor, vil vi maksimere profitten, og derfor velger vi varen med maksimal $ p_i / w_i $ , og legger den så mange stykker som mulig. Hvis vi går tom, velger vi varen med den nest største $ p_i / w_i $ , og så videre.

Du kan implementere dette uten å dele $ W $ i en $ 1000 $ stykker: Velg varen med maksimum $ p_i / w_i $ , og legg så mye av det som mulig. Hvis du går tom, velger du den neste og legger så mye av det som mulig. Og så videre. Å implementere denne algoritmen krever sortering av listen $ p_i / w_i $ , noe som tar tid $ O (n \ log n) $ . Algoritmen du beskriver bruker samme triksbruk i hurtigvalg for å redusere kjøretiden til $ O (n) $ , på bekostning av å gjøre algoritmen randomisert.

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

1. Forstå den klassiske grådige algoritmen for brøkdel av ryggsekk.
2. Forstå kvikkvalg.
3. Se hvordan algoritmen du siterer, kombinerer teknikken til hurtigvalg med den grådige tilnærmingen.

R er settet med forholdet mellom fortjeneste / vekt for hvert objekt , hvor fortjeneste og vekt av objekter er gitt. Og W er Kapasiteten til ryggsekken .
Nå, i stedet for å velge tilfeldig element i ett-trinn, kan vi bruke algoritme for medianfunn til finn median i O (n) ganger.
Og så kan vi gjøre resten av alle trinn.Så tidskompleksitetsanalysen vil være –
        T (n) = T (n / 2) + O (n).
Og vi får O (n) som løsning. Fortell meg om noe ikke er riktig forklart, og du vil vite noe mer.

I lineær tid kan du finne medianvare når det gjelder verdi per vektenhet. Deretter, også på lineær tid, kan du finne ut om du kan få plass til alle elementene som er minst like verdifulle i ryggsekken eller ikke. Hvis du kan, kan du gjøre det og løse dette problemet rekursivt for n / 2 gjenstander med lavere verdi gitt at du » har allerede fylt ryggsekken. Hvis du ikke kan «t, kan du kaste ut n / 2 elementene med lavere verdi, og prøv å løse problemet igjen med bare n / 2 elementene med høyest verdi.

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

I løsningen du har limt inn: R er settet med forholdstall, fortjeneste / vekt W er summeringen av hele vekten av dette settet , brukes til å sammenligne med kapasiteten til ryggsekken. Tilsvarende representerer {pi / wi | pi / wi} de ith-elementene profitten er til ith-vektverdien. Vi sammenligner denne verdien med den tilfeldig valgte r -verdien og skilles deretter ut basert på sammenligningen av forholdet. R1, R2, R3 er ytterligere delmengder av forholdet som er satt, avhengig av at forholdet er mindre, lik eller større enn for medianelementet.

på samme måte er W1, W2, W3 summeringen av vekten av disse settene.

Velg nå passende løsningssett avhengig av forholdsverdiene som forklart i starten.