Consider solving (approximately) the following knapsack problem by constructive search Algorithm 15A.

max 11x1 + 1x2 + 9x3 + 17x4 s.t. 9x1 + 2x2 + 7x3 + 13x4 … 17 x1,c, x4 = 0 or 1

(a) Determine a global optimum by inspection.

(b) Explain why it is reasonable to fix variables in decreasing order of ratio objective coefficient constraint coefficient

(c) Apply constructive search Algorithm 15A to construct an approximate solution choosing variables to fix in this ratio sequence.