Problem Description
Given a value V(change), and infinite supply of coins for each of C{C1,C2,C3 ? Cn}, find the minimum number of coins required to make the change.
Example) Given change 11 and coins {1,5,6,8} (each of them available in infinite supply), find the minimum number of coins required to make the change.
Solution : Possible combinations : {5,5,1},{6,5},{8,1,1,1} etc. The best solution is {6,5} since it requires only 2 coins.
Recursive Approach
On drawing the recursion tree, we can see overlapping subproblems.
Also, since ?optimal substructure? is a feature of the problem, we can find a solution using Dynamic Programming.
Building Auxiliary Storage and filling it
The first column has all values 0 because because the minimum number of coins to get change 0 is 0.
Consider the first row:
Cell(0,1) : The minimum number of coins to get change 1 when you can consider only coins of denomination 1 is 1 ({1}) .
Cell (0,2) : The minimum number of coins to get change 2 when you can consider only coins of denomination 1 is 2 ({1,1}).
So on and so forth till cell(0,11) in first row
Consider the second row:
Cells (1,0) ?. (1,4) -> one can copy values from the cell directly above since you cannot get change using coins having denomination greater that the value of the change itself. (example ? Cell(1,2) : get a change of 2 using coin of denomination 5 , hence we copy the solution from the cell directly above it which is Cell(0,2) . This means that the cell (1,2) holds the best possible solution to get a change 2 using coins of denominations 1 and 5)
Cell(1,5) : We can get the change 5 using a single coin of denomination 5 . Hence answer is 1.
Cell(1,6) : When we try to find a solution , we first take one coin of denomination 5. So, now we need to find the minimum number of coins required for 6?5=1. The solution for change 1 is given in Cell(1,1). Hence the answer is {1,5} and the minimum number of coins is 2.
In this way, we continue to fill the table row by row, from left to right.
In Cell(2,10) : To get change 10 using denomination 6 , one solution is {1,1,1,1,6} . This requires five coins. But this solution is not the best one. A better solution is {5,5} which has already been calculated in the cell above Cell(1,10). Hence, we copy that solution.
The answer is obtained from Cell(3,11).
References:
