Ułamkowy plecak w czasie liniowym

Byłoby miło, gdybyś przedstawił problem. Zakładam, że masz $ n $ elementy $ x_i $ , z których każdy ma zysk $ p_i $ i waga $ w_i $ . Chcesz zmaksymalizować swój zysk pod warunkiem, że całkowita waga nie przekracza $ W $ . Dla każdego elementu $ x_i $ możesz umieścić dowolny ułamek $ \ theta \ in [0,1] $ , co da ci zysk $ \ theta p_i $ i wagę $ \ theta w_i $ .

Oto przykład. Masz surowe złoto z zyskiem 1000 $ i wadze 1 $ . Masz także banany, z zyskiem 1 $ i wadze 10 $ . Załóżmy, że możesz przenosić ciężar 2 $ . Co byś zrobił? Oczywiście najpierw włożyłbyś tyle złota, ile możesz – mianowicie całe, a następnie włożyłbyś tyle bananów, ile możesz – mianowicie jedną dziesiątą tego, co daje całkowity zysk w wysokości 1000,1 $ .

Ogólny algorytm jest podobny. Załóżmy, że dzielisz $ W $ na 1000 $ „sloty”, które chcesz wypełnić najbardziej opłacalny element-części wagi W / 1000 $ . W przypadku towaru ważącego $ w_i $ mamy $ w_i / (W / 1000) $ sztuk (załóżmy na razie jest to liczba całkowita), a każda z nich jest warta $ p_i / (w_i / (W / 1000)) $ . Wybierając to, co umieścić w slocie, chcielibyśmy zmaksymalizować nasz zysk, dlatego wybieramy przedmiot z maksymalnym $ p_i / w_i $ i umieszczamy tyle sztuk, jak to możliwe. Jeśli się skończy, wybieramy element z następnym największym $ p_i / w_i $ i tak dalej.

Możesz to zaimplementować bez dzielenia $ W $ do $ 1000 $ sztuk: wybierz element z maksymalnym $ p_i / w_i $ i umieść tak dużo, jak to możliwe. Jeśli zabraknie, wybierz następny i włóż jak najwięcej. I tak dalej. Implementacja tego algorytmu wymaga posortowania listy $ p_i / w_i $ , co zajmuje czas $ O (n \ log n) $ . Algorytm, który opisujesz, wykorzystuje tę samą sztuczkę, której używasz w quickselect, aby skrócić czas działania do $ O (n) $ , kosztem zrandomizowania algorytmu.

Proponuję następującą drogę, aby zrozumieć algorytm:

1. Zrozum klasyczny algorytm zachłanny dla ułamkowego plecaka.
2. Zrozum szybki wybór.
3. Zobacz, jak cytowany przez Ciebie algorytm łączy technikę szybkiego wyboru z zachłannym podejściem.

R to zestaw stosunków zysku / wagi każdego przedmiotu , w którym podano zysk i wagę obiektów. A W to Pojemność plecaka .
Teraz zamiast wybierać losowy element w 1 kroku możemy zastosować algorytm znajdowania mediany do znajdź medianę za O (n) razy.
Następnie możemy wykonać resztę wszystkich kroków.Zatem analiza złożoności czasu będzie wyglądać następująco –
        T (n) = T (n / 2) + O (n).
I otrzymamy O (n) jako rozwiązanie. Powiedz mi, czy coś nie jest właściwie wyjaśnione i chcesz wiedzieć coś więcej.

W czasie liniowym możesz znaleźć mediana pozycji pod względem wartości na jednostkę wagi. Następnie, również w czasie liniowym, możesz dowiedzieć się, czy możesz zmieścić wszystkie przedmioty, które są co najmniej tak cenne w plecaku, czy nie. Jeśli możesz, zrób to i rekurencyjnie rozwiąż ten problem dla n / 2 elementów o niższej wartości, zakładając, że „ już wypełniliśmy plecak. Jeśli nie możesz, możesz wyrzucić n / 2 przedmioty o niższej wartości, a następnie spróbuj ponownie rozwiązać problem, używając tylko n / 2 elementów o największej wartości.

Tutaj powtarzalność to T (n) = T (n / 2) + O (n) , a mamy to T (n) = O (n) , zgodnie z życzeniem.

W wklejonym rozwiązaniu: R to zbiór wskaźników, zysk / waga W to suma całej wagi tego zbioru , używane do porównania z pojemnością Twojego plecaka. Podobnie {pi / wi | pi / wi} reprezentuje i-ty element zysku do i-tej wartości wagi. Porównujemy tę wartość z losowo wybraną wartością r , a następnie segregujemy na podstawie porównania współczynnika. R1, R2, R3 to kolejne podzbiory współczynnika w zależności od tego, czy stosunek jest mniejszy, równy lub większy niż element środkowy.