Rucsac fracționat în timp liniar

Ar fi frumos dacă ați declara problema. Presupun că aveți $ n $ articole $ x_i $ , fiecare având profit $ p_i $ și weight $ w_i $ . Doriți să vă maximizați profitul cu condiția ca greutatea totală să fie cel mult $ W $ . Pentru fiecare articol $ x_i $ , aveți permisiunea de a pune orice fracțiune $ \ theta \ în [0,1] $ din acesta, ceea ce vă va oferi profit $ \ theta p_i $ și greutate $ \ theta w_i $ .

Iată un exemplu. Aveți aur brut, cu un profit de $ 1000 $ și greutate $ 1 $ . De asemenea, aveți banane, cu un profit de $ 1 $ și greutate $ 10 $ . Să presupunem că puteți transporta o greutate de 2 $ $ . Ce ai face? Bineînțeles, ați pune mai întâi cât mai mult aur posibil – și anume, tot și apoi l-ați pune cât mai multe banane – și anume, o zecime din el, pentru un profit total de $ 1000,1 $ .

Algoritmul general este similar. Să presupunem că împărțiți $ W $ într-un $ 1000 $ „sloturi”, pe care doriți să le completați element profitabil-părți de greutate $ W / 1000 $ . Pentru un articol care cântărește $ w_i $ , avem $ w_i / (W / 1000) $ bucăți (să presupunem pentru momentul în care acesta este un număr întreg) și fiecare dintre ele valorează $ p_i / (w_i / (W / 1000)) $ . Atunci când alegem ce să punem într-un slot, am dori să ne maximizăm profitul și astfel alegem elementul cu $ p_i / w_i $ maxim și îl punem la fel de mult piese cât mai multe. Dacă ne epuizăm, alegem elementul cu următorul cel mai mare $ p_i / w_i $ și așa mai departe.

Puteți implementa acest lucru fără a împărți $ W $ într-o bucată $ 1000 $ : alegeți elementul cu $ p_i / w_i $ și puneți cât mai mult din acesta posibil. Dacă ai epuizat, alege-o pe următoarea și pune-o cât mai mult din ea. Și așa mai departe. Implementarea acestui algoritm necesită sortarea listei $ p_i / w_i $ , care necesită timp $ O (n \ log n) $ . Algoritmul pe care îl descrieți folosește același truc folosit în selectarea rapidă pentru a reduce timpul de rulare la $ O (n) $ , cu costul de a face algoritmul randomizat.

Vă sugerez următorul traseu pentru a înțelege algoritmul:

1. Înțelegeți algoritmul clasic lacom pentru rucsacul fracționat.
2. Înțelegeți selectarea rapidă.
3. Vedeți cum algoritmul pe care îl citați combină tehnica selectării rapide cu abordarea lacomă.

R este setul de rapoarte profit / greutate pentru fiecare obiect , în care sunt date profitul și greutatea obiectelor. Și W este Capacitatea rucsacului .
Acum, în loc să alegem elementul aleatoriu la un pas, putem aplica algoritmul de găsire median găsiți mediana în O (n) ori.
Și apoi putem face restul tuturor pașilor.Deci, analiza complexității timpului va fi –
        T (n) = T (n / 2) + O (n).
Și vom obține O (n) ca soluție. Spune-mi dacă ceva nu este explicat corect și vrei să afli ceva mai mult.

În timp liniar, poți găsi element median în termeni de valoare pe unitate de greutate. Apoi, de asemenea, în timp liniar, vă puteți da seama dacă puteți încadra toate articolele care sunt cel puțin atât de valoroase în rucsac sau nu. Dacă puteți, faceți acest lucru și rezolvați recursiv această problemă pentru n / 2 elemente cu valoare mai mică având în vedere că ” Am umplut deja rucsacul. Dacă nu poți, atunci poți arunca n / 2 elemente cu valoare mai mică, și apoi încercați să rezolvați problema din nou numai cu n / 2 elemente de cea mai mare valoare.

Recurența aici este T (n) = T (n / 2) + O (n) și avem acel T (n) = O (n) , după dorință.

În soluția pe care ați lipit-o: R este setul de rapoarte, profit / pondere W este însumarea întregii ponderi a acestui set , folosit pentru a compara cu capacitatea rucsacului tău. În mod similar, {pi / wi | pi / wi} reprezintă elementele ith profitul este până la valoarea ponderii ith. Comparăm această valoare cu valoarea r selectată aleatoriu și apoi separăm pe baza comparației raportului. R1, R2, R3 sunt alte subseturi ale raportului setat în funcție de raportul fiind mai mic, egal sau mai mare decât cel al elementul median.

în mod similar, W1, W2, W3 sunt însumarea ponderilor acestor seturi.

Acum alegeți soluția potrivită setată în funcție de valorile raportului, așa cum se explică la început.