Coin Change — Minimum Number of Coins — Dynamic Programming Solution

Coin Change — Minimum Number of Coins — Dynamic Programming Solution

Image for post

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

Image for post

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

Image for post

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:

Find minimum number of coins that make a given value – GeeksforGeeks

Given a value V, if we want to make change for V cents, and we have infinite supply of each of C = { C1, C2, .. , Cm}?

www.geeksforgeeks.org

No Responses

Write a response