a. Apply the dynamic programming algorithm to the followinginstance of the 0-1 knapsack problem:
Item ?? Weight Value
1 ?? 3 $30
2 2 ?? ? $20
3 1 $15
4 4 ? $40
5 5 ? $50
with capacity W = 6.
Show your pseudo codes for the dynamic programming solution.
You should include a procedure to retrieve an optimalsolution.
b. How many different optimal subsets does the instance of part(a) have? Show all optimal subsets.
c. In general, how can we use the table generated by the dynamicprogramming algorithm to tell whether there is more than oneoptimal subset for the knapsack problem’s instance?