Fractional Knapsack in linear time

Question

How to solve fractional knapsack in linear time? I found this on Google but don't really understand it.

1. Choose element $r$ at random from $R$ (set of profit/weight ratios)
2. 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$
3. if $W_1 > W$
   • recurse $R_1$ and return computed solution
4. else
   • while (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?

Answer 1

It would be nice if you stated the problem. I assume that you have $n$ items $x_i$, each having profit $p_i$ and weight $w_i$. You want to maximize your profit under the constraint that the total weight is at most $W$. For each item $x_i$, you are allowed to put any fraction $\theta \in [0,1]$ of it, which will give you profit $\theta p_i$ and weight $\theta w_i$.

Here is an example. You have raw gold, with a profit of $1000$ and weight $1$. You also have bananas, with a profit of $1$ and weight $10$. Suppose you can carry a weight of $2$. What would you do? Naturally, you would first put as much gold as you can - namely, all of it, and then you would put it as many bananas as you can - namely, a tenth of it, for a total profit of $1000.1$.

The general algorithm is similar. Suppose you divide $W$ into a $1000$ "slots", which you want to fill with the most profitable item-parts of weight $W/1000$. For an item weighing $w_i$, we have $w_i/(W/1000)$ pieces (suppose for the moment that this is an integer), and each of them is worth $p_i/(w_i/(W/1000))$. When choosing what to put in a slot, we would like to maximize our profit, and so we choose the item with maximal $p_i/w_i$, and put it as many pieces as possible. If we run out, we choose the item with the next largest $p_i/w_i$, and so on.

You can implement this without dividing $W$ into a $1000$ pieces: Choose the item with maximal $p_i/w_i$, and put as much of it as possible. If you run out, choose the next one, and put as much of it as possible. And so on. Implementing this algorithm requires sorting the list $p_i/w_i$, which takes time $O(n\log n)$. The algorithm you describe uses the same trick use in quickselect to reduce the running time to $O(n)$, at the cost of making the algorithm randomized.

I suggest the following route to understand the algorithm:

1. Understand the classical greedy algorithm for fractional knapsack.
2. Understand quickselect.
3. See how the algorithm you quote combines the technique of quickselect with the greedy approach.

Answer 2

R is the set of ratios of profit/ weight of every object, where profit and weight of objects are given. And W is the Capacity of knapsack.
Now Instead of choosing random element at 1-step we can apply median finding algorithm to find median in O(n) times.
And then we can do rest of all steps. So the time complexity analysis will be -
       T(n) = T(n/2) + O(n).
And we will get O(n) as solution. Tell me if anything is not properly explained and you wanna know something more.

Answer 3

In linear time, you can find the median item in terms of value per unit weight. Then, also in linear time, you can figure out if you can fit all items that are at least that valuable in the knapsack or not. If you can, then do so, and recursively solve this problem for the n/2 items of lower value given that you've already filled the knapsack. If you can't, then you can throw out the n/2 items of lower value, and then try to solve the problem again with only the n/2 items of highest value.

The recurrence here is T(n)=T(n/2)+O(n), and we have that T(n)=O(n), as desired.

In the solution you have pasted: R is the set of ratios, profit/weight W is the summation of the entire weight of this set, used to compare with the capacity of your knapsack. Similarly, {pi/wi|pi/wi} represents the ith elements profit is to the ith weight value. We are comparing this value to the randomly selected r value and then segregating based on the comparison of the ratio. The R1, R2, R3 are further subsets of the ratio set depending on the ratio being less, equal or greater than that of the median element.

similarly, the W1, W2, W3 are the summation of the weights of these sets.

Now choose the suitable solution set depending on the ratio values as explained in starting.

Answer 4

I tried to implement the algorithm in c++. Here is the link Fractional knapsack in linear time