Given an unlimited supply of coins of denominations x1,x2…,we wish to make change for a value v using not more than k coins…
Please tell me the solution…
**EDIT:**I need to know the number of ways to do so…
6.19. Here is yet another variation on the change-making problem (Exercise 6.17).
Given an unlimited supply of coins of denominations x1; x2; : : : ; 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 efcient dynamic-programming algorithm for the
Input: x1; : : : ; xn; k; v.
Question: Is it possible to make change for v using at most k coins, of denominations
x1; : : : ; xn?