Consider the following instance of the knapsack problem: number of jobs n = 4; Capacity of the knapsack M= 9, profits (p1, P2, P3, P4) = (2, 4, 6, 8) and weights (W, W2, W3, W4) =(4, 3, 2, 1). (a) (3 points) First explain basic idea of the following dynamic programming formulation: fi(y) = max {fi-1(y), fi-1(y wi) + Pi} (b) (10 points) Then develop the set solution by developing all sets, show purging as you develop sets. Discuss all your work, specially explaining the idea of purging. (c) (2 points) Finally use the above sets to find the optimal solution when capacity of knapsack is 9. Show all your work.