Fractional Knapsack Problem
Introduction In the fractional knapsack problem, the setup is the same in the 0-1 knapsack problem, but the thief can take fractions of items, rather than having to make a binary (0, 1) choice for each item. You can think of an item in the 0-1 knapsack problem as being like a gold ingot and an item in the fractional knapsack problem as more like gold dust. [1] We can solve the fractional knapsack problem by a greedy strategy. To solve the fractional problem, we first compute the value per pound, $v_i/w_i$ for each item. Obeying a greedy strategy, the thief begins by taking as much as possible of the item with the greatest value per pound. If the supply of that item is exhausted, and he can still carry more, he takes as much as possible of the item with the next greatest value per pound, and so forth. [1] Now let’s draw our attention to an exercise in the CLRS book [1]. Exercise 16.2-6 Show how to solve the fractional knapsack problem in $O(n)$ time. [1] By sorting the items by value pe...