1. **Problem Statement:** We have a variant of the 0-1 knapsack problem with capacity $S$ and $n$ items. Each item $a_i$ can be accepted fully, rejected, or half-accepted. Half-accepting means taking half the size $\frac{s_i}{2}$ and gaining half the value $\frac{v_i}{2}$. We define $V(T,m)$ as the optimal profit for the first $m$ items with capacity $T$. We need to identify the correct recursive formula and boundary conditions for $V(T,m)$. 2. **Key Formula and Explanation:** The classical knapsack recurrence for full acceptance or rejection is: $$ V(T,m) = \max \{ V(T,m-1), V(T - s_m, m-1) + v_m \} $$ Here, $V(T,m-1)$ means rejecting item $m$, and $V(T - s_m, m-1) + v_m$ means accepting it fully if capacity allows. 3. **Extension for Half-Acceptance:** Since half-acceptance is allowed, we add the option: $$ V(T,m) = \max \{ V(T,m-1), V(T - s_m, m-1) + v_m, V(T - \frac{s_m}{2}, m-1) + \frac{v_m}{2} \} $$ This means we choose the best among rejecting, fully accepting, or half-accepting item $m$. 4. **Check the Options:** - (a) uses $\min$ and subtracts $v_m$ from $T$, which is incorrect because capacity is reduced by size $s_m$, not value $v_m$. - (b) uses $\max$ and correctly subtracts sizes $s_m$ and $\frac{s_m}{2}$ from $T$, adding corresponding values $v_m$ and $\frac{v_m}{2}$. This matches the correct formula. - (c) is the classical knapsack without half-acceptance, so it is correct but incomplete for this variant. - (d) uses $\min$ instead of $\max$, incorrect. - (e) uses $\max$ but subtracts $v_m$ from $T$ instead of $s_m$, incorrect. - (f) states $V(T,1) = 0$ if $s_1 > T$, which is correct because if the first item doesn't fit, profit is zero. - (g) uses $v_m$ subtracted from $T$, incorrect. - (h) is false because some choices are correct. - (i) states $V(0,m) = 0$, which is correct since zero capacity means zero profit. 5. **Summary of Correct Statements:** (b), (f), and (i) are correct. 6. **Final Answer:** - The correct recursive formula is (b): $$ V(T,m) = \max \{ V(T,m-1), V(T - s_m, m-1) + v_m, V(T - \frac{s_m}{2}, m-1) + \frac{v_m}{2} \} $$ - Boundary conditions: $$ V(T,1) = 0 \text{ if } s_1 > T $$ $$ V(0,m) = 0 $$