PART B more importantly!

a Given an unlimited supply of coins of denominations r1, r2,... ,Xn, we wish to make change for a value v; that is, we wish to find a set of coins whose total value is v. This might not be possible: for instance, if the denominations are 5 and 10 then we can make change for 15 but not for 12. Give an O(nv) dynamic-programming algorithm for the following problerm . Input: x1, ,Tm u. Question: Is it possible to make change for v using coins of denominations b Consider the following variation on the change-making problem above. You are given denominations z1, T2, '-- , Tn, and you want to make change for a value v, but you are allowed to use each denomination at most once. For instance, if the denominations are 1, 5, 10, 20, then you can make change for 16 1 + 15 and for 31 1 + 10 + 20 but not for 40 (because you cant use 20 twice) . Input: Positive integers 2:1,T2, ,xn. another integer u. Output: Can you make change for u, using each denomination xi at most once? Show how to solve this problem in time O(nv) For each algorithm, provide an intuitive argument on why your algorithm is correct and analyze its run-time