Consider the following instance of the knapsack problem with capacity W = 6 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 problems 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). f) 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.

Item Weight Value $25 $20 $15 $40 $50