Chapter 35, Problem 7P

a

Program Plan Intro

To argue that the solution to instance I of the 0-1 knapsack problem is one of $\left\{P_1,P_1,\mathrm{.......},P_n\right\}$ .

b

Program Plan Intro

To prove that an optimal solution $Q_j$ can be found to the fractional problem using the greedy algorithm.

c

Program Plan Intro

To prove that that an optimal solution $Q_j$ can be always constructed to the fractional problem for instance $I_j$ that includes at most one item fractionally.

c

Program Plan Intro

Toprove that $\upsilon \left(R_j\right)\ge \upsilon \left(Q_j\right)/2\ge \upsilon \left(P_j\right)/2$ .

d

Program Plan Intro

To give a polynomial-time algorithm that returns a maximum-value solution from the set $\left\{R_1,R_2,\mathrm{......},R_n\right\}$ and also prove that the algorithm is a polynomial time 2-approximation algorithm for the 0-1 knapsack problem.