algorithm

Problem 3 (20 points) Consider the following simplified version of 0-1 knapsack. Suppose you enter a store where there are n objects with values Vi, 12...., Vn, respectively. This time you are not limited by the capacity of your knapsack but you need to pick objects so that the sum of their values is equal to a target value V. Thus the sum of the values cannot be more or less) than V. It has to be exactly equal to V. If this is not possible, your algorithm should report so, For example, consider the table shown alongside. If V=10, you can return objects 2,3 and 5 or objects 3,4 since both choices Obj1 Obj 2 Obj 3 Obj 4 Obj5 achieve a value of 10. However, if V-12 no solution exists. Value 3 2 5 Design a Dynamic Programming solution for this problem. Define OPTIK, v to be TRUE if it's possible to select among the first k objects a subset of the objects whose sum of values is equal to v. If this is not possible, OPT[k, v) should be FALSE. a) (5 points) Give a recursive definition for OPTIA, V) and argue about its correctness (remember OPTIX, v) can be either TRUE or FALSE). Clearly mention the steps you followed in order to arrive at the recurrence. b) (5 points) How many subproblems are there? The solution of subproblem OPT[K, v] depends upon the solution of which subproblems? How did you obtain this relationship? c) [5 points] Give pseudocode (no program) for a dynamic programming algorithm to calculate OPT[n, 7). What is the running time of your dynamic programming algorithm? You need to analyze the various steps of your algorithm. d) [5 points] How would you modify your algorithm in part (c) so that it returns the actual objects rather than just whether it is possible to achieve the target value V? Clearly identify the changes and argue about their correctness