Coin Change Problem: Minimum number of coins to change an amount.

You are given 4 coins of {1, 5, 6, 9} denominations with the infinite number of coins. Now find out the minimum number of coins that can make 10. That’s means to find out the minimum number of coins to change 10. 

 

Answer:

The first row is weight from 0 to 10 because here we are finding the minimum number of coins to change 10 and the first column is the available coins. 

	0	1	2	3	4	5	6	7	8	9	10
1	0	1	2	3	4	5	6	7	8	9	10
5	0	1	2	3	4	min(5, 1) =1	min(6, 2) =2	min(7, 3) =3	min(8, 4) =4	min(9, 5) =5	min(10, 2) =2
6	0	1	2	3	4	1	min(2, 1) =1	min(3, 2) =2	min(4, 3) =3	min(5, 4) =4	min(2, 2) =2
9	0	1	2	3	4	1	1	2	3	min(4, 1) =1	min(2, 2) =2

 

So the answer is 2

 

If the coin value > w the just copy the above value.

• matrix[i][j] = matrix[i - 1][j]

If coin value is not less then w then do the following task.

• matrix[i][j] = min( matrix[i - 1][j],  1 + matrix[i][j - coins[I]] )

 

Python Implementation:

def min_coins(coins, weight):
    coins.sort()
    matrix = [[0 for _ in range(weight + 1)] for j in range(len(coins))]
    matrix[0][0] = 0
    for j in range(1, weight + 1):
        if j % coins[0] == 0:
            matrix[0][j] = j // coins[0]

    for i in range(1, len(matrix)):
        for j in range(weight + 1):
            if coins[i] > j:
                matrix[i][j] = matrix[i - 1][j]
            else:
                matrix[i][j] = min(matrix[i - 1][j], 1 + matrix[i][j - coins[i]])

    return matrix[-1][-1]


if __name__ == '__main__':
    available_coins = [1, 5, 6, 9]
    total = 24
    print(min_coins(available_coins, total))

Output: 2

Time complexity: O(n * w)