Standard Coin denomination problem is as follows
coin set = {1,2,5,10 ... } - each coin count is unlimited
find count of possible combinations of coins to create N Rs
This problem can either be done using backtracking or dynamic programming
Now My requirement added a factor where max count of each coin is given e.g.
{ (1, 10), (2, 5), (5, 4), (10, 100) } where (n,m) denotes m coins are of each n Rupees.
This can be done using backtracking by an addition check while inserting element to stack but this takes exponential time. Can somebody provides solution using dynamic programming ?
thanks in advance..