ANSWER EITHER THIS QUESTION OR QUESTION 3 Consider the problem of taking a set of n items with sizes s1,,sn, and values v1,,vn respectively. We assume si,viN for all 1in. Suppose we are also given a "knapsack capacity" CN. The knapsack problem is the problem of finding a subset S{1,,n} such that iSsiC and such that iSvi is maximized subject to the first constraint. We write Pn,C to denote the value iSvi of the maximum-value knapsack on the set of all items. For any kn, and any CC,CN, we can consider the same problem on the first k items in regard to capacity C. We denote the maximum-value knapsack for such a subproblem by Pk,C^. (a) Prove that the following recurrence holds: Pk,C^=0Pk1,Cmax{Pk1,C,Pk1,Csk+vk}ifk=0ifk>0butsk>Cotherwise. [10r (b) Use the recurrence above to develop a (nC) dynamic programming algorithm to compute the optimal knapsack wrt. the original n items and capacity C. Justify the (nC) runtime of your algorithm. [15n