Exercise 11.11. Consider the 0/1 Knapsack problem with two knapsacks having capacities mi and m2 respectively. We haven items x1,.., Xn. Item ai has an associated weightwi and profitp,. The goal is to fill as many items as possible in the two knapsacks so that we maximize the total profit. An item can be chosen to be put in either of the two knapsacks (if possible) or not chosen at all. Assume that weights, profits, mi, and m2 are all positive integers. (i) Show that the optimal substructure property holds for the problem. (i) Let flvi,32) be the optimal solution for the subproblem restricted to the first i items x1,.. . , Ti such that the two knapsacks have capacities yi and y2 respectively Give a recursive formulation for computing fi(i, y2 a DP algorithm or a memoized algorithm. Analyze the running time of your algorithm (iv) Describe how to change the algorithm so that it also generates the optimum solution (i.e., which items are chosen and in uluch knapsack)