See how the algorithm you quote combines the technique of quickselect with the greedy approach.Understand the classical greedy algorithm for fractional knapsack.I suggest the following route to understand the algorithm: 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. Implementing this algorithm requires sorting the list $p_i/w_i$, which takes time $O(n\log n)$. If you run out, choose the next one, and put as much of it as possible. 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 we run out, we choose the item with the next largest $p_i/w_i$, and so on.
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. 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))$. Suppose you divide $W$ into a $1000$ "slots", which you want to fill with the most profitable item-parts of weight $W/1000$. 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$.
You also have bananas, with a profit of $1$ and weight $10$. You have raw gold, with a profit of $1000$ and weight $1$. For each item $x_i$, you are allowed to put any fraction $\theta \in $ of it, which will give you profit $\theta p_i$ and weight $\theta w_i$.
You want to maximize your profit under the constraint that the total weight is at most $W$. I assume that you have $n$ items $x_i$, each having profit $p_i$ and weight $w_i$. It would be nice if you stated the problem.
0 kommentar(er)
