Give a greedy algorithm for the fractional knapsack problem

Give a greedy algorithm for the fractional knapsack problem. To show its correctness give a rigorous proof that always making a greedy choice leads to an optimal solution.

Solution

Greedy-fractional-knapsack (w, v, W)

FOR i =1 to n
    do x[i] =0
weight = 0
while weight < W
    do i = best remaining item
        IF weight + w[i] W
            then x[i] = 1
                weight = weight + w[i]
            else
                x[i] = (w - weight) / w[i]
                weight = W
return x

Analysis  

If the items are already sorted into decreasing order of v_i / w_i, then
            the while-loop takes a time in O(n);
Therefore, the total time including the sort is in O(n log n).

If we keep the items in heap with largest v_i/w_i at the root. Then

creating the heap takes O(n) time

while-loop now takes O(log n) time

The optimal solution to this problem is to sort by the value of the item in decreasing order. Then pick up the most valuable item which also has a least weight. First, if its weight is less than the total weight that can be carried. Then deduct the total weight that can be carried by the weight of the item just pick. The second item to pick is the most valuable item among those remaining. Keep follow the same strategy until thief cannot carry more item (due to weight).

Proof

One way to proof the correctness of the above algorithm is to prove the greedy choice property and optimal substructure property. It consist of two steps. First, prove that there exists an optimal solution begins with the greedy choice given above. The second part prove that if A is an optimal solution to the original problem S, then A - a is also an optimal solution to the problem S - s where a is the item thief picked as in the greedy choice and S - s is the subproblem after the first greedy choice has been made. The second part is easy to prove since the more valuable items have less weight.
Note that if v` / w`, is not it can replace any other because w` < w, but it increases the value because v` > v.