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..