Consider the following instance of the knapsack problem with capacity W = 6...

Consider the following instance of the knapsack problem with capacity W = 6 Item Weight Value $25 $20 $15 4 $40 5 5 $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). Consider the following instance of the knapsack problem with capacity W = 6 Item Weight Value $25 $20 $15 4 $40 5 5 $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)