Recall the knapsack problem from Section 16.2. There are n items, where the i th item is worth ν_i dollars and weighs w_i pounds. We are also given a knapsack that can hold at most W pounds. Here, we add the further assumptions that each weight w_i is at most W and that the items are indexed in monotonically decreasing order of their values. ν₁ ≥ ν₂ ≥ ··· ≥ ν_n.

In the 0-1 knapsack problem, we wish to find a subset of the items whose total weight is at most W and whose total value is maximum. The fractional knapsack problem is like the 0-1 knapsack problem, except that we are allowed to take a fraction of each item, rather than being restricted to taking either all or none of each item. If we take a fraction x_i of item i, where 0 ≤ x_i ≤ 1, we contribute x_iw_i to the weight of the knapsack and receive value x_iν_i. Our goal is to develop a polynomial-time 2-approximation algorithm for the 0-1 knapsack problem.

In order to design a polynomial-time algorithm, we consider restricted instances of the 0-1 knapsack problem. Given an instance I of the knapsack problem, we form restricted instances I_j, for j = 1, 2, . . . ,n, by removing items 1, 2, . . . ,j – 1 and requiring the solution to include item j (all of item j in both the fractional and 0-1 knapsack problems). No items are removed in instance I₁. For instance I_j, let P_j denote an optimal solution to the 0-1 problem and Q_j denote an optimal solution to the fractional problem.

a. Argue that an optimal solution to instance I of the 0-1 knapsack problem is one of {P₁, P₂, . . . ,P_n}.

b. Prove that we can find an optimal solution Q_j to the fractional problem for instance I_j by including item j and then using the greedy algorithm in which at each step, we take as much as possible of the unchosen item in the set {j + 1, j + 2, . . . ,n} with maximum value per pound ν_i/w_i.

c. Prove that we can always construct an optimal solution Q_j to the fractional problem for instance I_j that includes at most one item fractionally. That is, for all items except possibly one, we either include all of the item or none of the item in the knapsack.

d. Given an optimal solution Q_j to the fractional problem for instance I_j, form solution R_j from Q_j by deleting any fractional items from Q_j. Let ν(S) denote the total value of items taken in a solution S. Prove that ν(R_j) ≥ ν(Q_j)/2 ≥ ν(P_j)/2.

e. Give a polynomial-time algorithm that returns a maximum-value solution from the set {R₁, R₂, . . . ,R_n}, and prove that your algorithm is a polynomial-time 2-approximation algorithm for the 0-1 knapsack problem.