Given an unlimited supply of coins in denominations x1, , xn we wish to make change for a value v using at most k coins. That is, we wish to find a set of k coins whose total value is v. This might not be possible, for instance if the denominations are 5 and 10 and k =6, then we can make change for 55 but not for 65.

Give an O(nv) dynamic programing algorithm for the following problem

Input: x1, , xn; k; v

Is it possible to make change for v using at most k coins of denominations of x1, , xn?