Data Structures, Algorithms, & Applications in C++
Chapter 17, Exercise 17

(a)

The profit densities are [0.2, 1.5, 1.5]. Therefore we consider the objects in the order 2, 3, 1. Objects 2 and 3 are packed and then 0.85 of object 2 is packed. The solution is x = [0.85, 1, 1] and the profit earned from the packing is 47.

(b)

Consider any instance of the continuous knapsack problem. We may assume that the objects are given in nonincreasing order of profit density. Let x1 ... xn be the greedy solution and let y1 ... yn be an optimal solution. We shall show that both solutions earn the same profit and so the greedy solution is also optimal.

Let j be the least integer such that xi = yi, 1 <= i < j and xj != yj. If no such j exists, the two solutions are the same and so the greedy solution is optimal. Assume such a j exists. From the way the greedy algorithm works and the fact that the optimal solution is a feasible solution, we conclude that xj > yj. If we increase the fraction of object j in the optimal solution to xj and reduce the fraction of objects j+1, j+2, ... to compensate for the increased weight used by object j, the profit cannot decrease because we are replacing lower density fractions by higher or equal density ones. This transformation, therefore, yields a new optimal solution for which the least integer j such that xi = yi, 1 <= i < j and xj != yj (if it exists) is larger than for the old optimal solution.

By applying this transformation a finite number of times, we convert the original optimal solution into the greedy solution without decreasing the profit earned. So the greedy solution must also be optimal.