How to solve fractional knapsack in linear time? I found this on Google but don't really understand it. Choose element $r$ at random from $R$ (set of profit/weight ratios)Determine$R_1 = \{ p_i / w_i | p_i / w_i > r, for 1 \leq i \leq n \}, W_1 = \sum_{i \in R_1} w_i$$R_2 = \{ p_i / w_i | p_i / w_i = r, for 1 \leq i \leq n \}, W_2 = \sum_{i \in R_3} w_i$$R_3 = \{ p_i / w_i | p_i / w_i < r, for 1 \leq i \leq n \}, W_3 = \sum_{i \in R_3} w_i$if $W_1 > W$recurse $R_1$ and return computed solutionelsewhile (there's space in knapsack and $R_2$ is not empty)add items from $R_2$if (knapsack gets full)return items in $R_1$ and items just added from $R_2$else reduce knapsack capacity by $W_1 + W_2$recurse on $R_3$ and return items in $R_1 \cup R_2$add items returned from recursive call I don't get how it works, what $R$ and $W$ are supposed to represent ... can someone explain? Or maybe if you have another algorithm to propose? 
Fractional Knapsack in linear time
algorithms;algorithm analysis;greedy algorithms