Problem 4. (14 points) Consider the following instance of the knapsack problem with capacity W = 6 Item Weight Value $25 $20 $15 $40 $50 a) Apply the bottom-up dynamic programming algorithm to that instance. b) How many different optimal subsets does the instance of part (a) have? c) In general, how can we use the table generated by the dynamic programming algorithm to tell whether there is more than one optimal subset for the knapsack problem s instance? d) Implement the bottom-up dynamic programming algorithm for the knapsack problem. The program should read inputs from a file called "data.txt", and the output will be written to screen, indicating the optimal subset(s); e) For the bottom-up dynamic programming algorithm, prove that its time efficiency is in (nW), its space efficiency is in (nW) and the time needed to find the composition of an optimal subset from a filled dynamic programming table is in O(n). EXTRA CREDIT (4 points) Implement an algorithm that finds the composition of an optimal subset from the table generated by the bottom-up dynamic programming algorithm for the knapsack problem Programs can be written in C, C+ or Python, but all code must run on the