Now consider knapsack instance max 30x1 + 20x2 + 20x3 s.t. 21x1 + 20x2 + 20x3 … 40 x1, x2, x3 = 0 or 1

(a) Determine a global optimum by inspection

(b) Now apply Constructive Search Algorithm l5A with the greedy ratio of Exercise l5-l

(b) to compute an approximate optimum.

(c) Compare the results of

(a) and (b), and discuss how the local nature of greedy ratio search led part

(b) to a poorer solution.