35-7 An approximation algorithm for the 0-1 knapsack problem

Recall the knapsack problem from Section 16.2. There are $n$ items, where the $i$th item is worth $v_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: $v_1 \ge v_2 \ge \cdots \ge v_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 \le x_i \le 1$, we contribute $x_iw_i$ to the weight of the knapsack and receive value $x_iv_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, \dots, n$, by removing items $1, 2, \dots, 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_1$. 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_1, P_2, \dots, 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, \dots, n\}$ with maximum value per pound $v_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 $v(S)$ denote the total value of items taken in a solution $S$. Prove that $v(R_j) \ge v(Q_j) / 2 \ge v(P_j) / 2$.

e. Give a polynomial-time algorithm that returns a maximum-value solution from the set $\{R_1, R_2, \dots, R_n\}$, and prove that your algorithm is a polynomial-time $2$-approximation algorithm for the 0-1 knapsack problem.

(Omit!)