Fractionele knapzak in lineaire tijd

Het zou fijn zijn als u het probleem zou aangeven. Ik neem aan dat u $ n $ items $ x_i $ hebt, die elk $ p_i $ en gewicht $ w_i $ . U wilt uw winst maximaliseren onder de voorwaarde dat het totale gewicht maximaal $ W $ is. Voor elk item $ x_i $ mag u elke breuk $ \ theta \ in [0,1] $ ervan, waarmee u $ \ theta p_i $ en het gewicht $ \ theta w_i $ .

Hier is een voorbeeld. U heeft onbewerkt goud met een winst van $ 1000 $ en een gewicht $ 1 $ . Je hebt ook bananen, met een winst van $ 1 $ en een gewicht $ 10 $ . Stel dat u een gewicht van $ 2 $ kunt dragen. Wat zou jij doen? Natuurlijk zou je eerst zoveel mogelijk goud plaatsen – namelijk alles, en dan zou je er zoveel mogelijk bananen in doen – namelijk een tiende ervan, voor een totale winst van $ 1000,1 $ .

Het algemene algoritme is vergelijkbaar. Stel dat u $ W $ verdeelt in een $ 1000 $ “slots”, die u zo veel mogelijk wilt vullen winstgevende item-gewichtsdelen $ W / 1000 $ . Voor een artikel dat $ w_i $ weegt, hebben we $ w_i / (W / 1000) $ stuks (stel dat op het moment dat dit een geheel getal is), en elk van hen is $ p_i / (w_i / (W / 1000)) $ waard. Bij het kiezen van wat we in een slot plaatsen, willen we onze winst maximaliseren, en daarom kiezen we het item met maximale $ p_i / w_i $ , en plaatsen er zoveel stukken mogelijk. Als we opraken, kiezen we het item met de volgende grootste $ p_i / w_i $ , enzovoort.

U kunt dit implementeren zonder te verdelen $ W $ in een $ 1000 $ stukken: kies het item met de maximale $ p_i / w_i $ , en plaats er zoveel mogelijk van. Als je opraakt, kies dan de volgende en doe er zoveel mogelijk van. Enzovoort. Om dit algoritme te implementeren, moet de lijst $ p_i / w_i $ worden gesorteerd, wat tijd kost $ O (n \ log n) $ . Het algoritme dat u beschrijft, gebruikt dezelfde truc als in quickselect om de looptijd te verkorten tot $ O (n) $ , ten koste van het willekeurig maken van het algoritme.

Ik stel de volgende route voor om het algoritme te begrijpen:

1. Begrijp het klassieke hebzuchtige algoritme voor fractionele knapzak.
2. Begrijp quickselect.
3. Zie hoe het algoritme dat u citeert de techniek van quickselect combineert met de hebzuchtige benadering.

R is de set van ratios van winst / gewicht van elk object , waarbij winst en gewicht van objecten worden gegeven. En W is de capaciteit van knapzak .
Nu, in plaats van een willekeurig element in 1 stap te kiezen, kunnen we mediaan zoekalgoritme toepassen op vind mediaan in O (n) keer.
En dan kunnen we de rest van alle stappen uitvoeren.De analyse van de tijdcomplexiteit is dus –
        T (n) = T (n / 2) + O (n).
En we krijgen O (n) als oplossing. Vertel me als iets niet goed wordt uitgelegd en je iets meer wilt weten.

In lineaire tijd kun je de mediaan item in termen van waarde per gewichtseenheid. Dan kun je, ook in lineaire tijd, uitzoeken of je alle items die minstens zo waardevol zijn in de knapzak kunt passen of niet. Als je kunt, doe dat dan en los dit probleem recursief op voor de n / 2 items met een lagere waarde aangezien je ” hebben de knapzak al gevuld. Als je t kunt, dan kun je de n / 2 items met een lagere waarde weggooien, en probeer dan het probleem opnieuw op te lossen met alleen de n / 2 items met de hoogste waarde.

De herhaling hier is T (n) = T (n / 2) + O (n) , en dat hebben we T (n) = O (n) , zoals gewenst.

In de oplossing die je hebt geplakt: R is de set verhoudingen, winst / gewicht W is de som van het volledige gewicht van deze set , gebruikt om te vergelijken met de capaciteit van uw knapzak. Evenzo vertegenwoordigt {pi / wi | pi / wi} de ie elementen winst is ten opzichte van de ie gewichtswaarde. We vergelijken deze waarde met de willekeurig geselecteerde r waarde en scheiden vervolgens op basis van de vergelijking van de ratio. De R1, R2, R3 zijn verdere subsets van de ingestelde ratio, afhankelijk van of de ratio kleiner, gelijk of groter is dan die van het mediaan element.

op dezelfde manier zijn de W1, W2, W3 de som van de gewichten van deze sets.

Kies nu de geschikte oplossingsset afhankelijk van de verhoudingswaarden zoals uitgelegd in starten.