25. Consider the Knapsack problem with n items and a knapsack size W. Let $(a_1,b_1), (a_2,b_2), \ldots, (a_n,b_n)$ be the size and profit of the items in order, i.e., $a_i$ is the size of the $i^{th}$ item and $b_i$ is its profit.

(a) (2%). Consider the following simple greedy algorithm.

• $C \leftarrow \emptyset$, $S \leftarrow \{1,2,\ldots,n\}$.
• Repeat until $S = \emptyset$, do
  • Find $i \in S$ with the maximum profit-cost ratio. That is, $\frac{b_i}{a_i} = \max_{j \in S} \frac{b_j}{a_j}$.
  • Add i to C if $a_i + size(C) \le W$.
  • Remove i from S.

Does this algorithm correctly compute an optimal solution for the Knapsack problem? If so, briefly justify its correctness. If not, provide a counter-example with the smallest number of items.

(b) (2%). For any i and w with $0 \le i \le n$ and $w \ge 0$, define $A(i,w)$ to be the maximum profit we can obtain, if we are using only the first i items and the knapsack size is w. Consider the following recurrence formula for $A(i,w)$.

$A(i,w) = \begin{cases} -\infty, & \text{if } w < 0, \\ 0, & \text{if } w \ge 0, i = 0, \\ \max(A(i-1,w),\ A(i-1,w-a_i)+b_i), & \text{if } w \ge 0, i > 0. \end{cases}$

Suppose that W = 5 and we have 3 items with size and profit (4,20), (2,8), (3,14). Use the recurrence to calculate the value $A(i,w)$ for all $0 \le i \le 3$ and $0 \le w \le 5$ in a table, as shown below. What is the optimal profit?