Question

Python Coding Question: Find the minimum number of coins that make a given value.

Answer 1

Python Code:

import sys  
  
# l is size of coins array (number of different coins) 
def minimumCoins(coins, l, value): 
      
    # table[i] will be storing the minimum number of coins required for i value.  
    # So table[value] will have result 
    table = [0 for i in range(value + 1)] 
  
    # Base case (If given value is 0) 
    table[0] = 0
  
    # Initialize all table values as Infinite 
    for i in range(1, value + 1): 
        table[i] = sys.maxsize 
  
    # Compute minimum coins required for all values from 1 to value 
    for i in range(1, value + 1): 
          
        # Go through all coins smaller than i 
        for j in range(l): 
            if (coins[j] <= i): 
                sub_result = table[i - coins[j]] 
                if (sub_result != sys.maxsize and sub_result + 1 < table[i]): 
                    table[i] = sub_result + 1
    return table[value] 
  
# We will take the coin denominations to be 1,5,10
# The denominations can be chosen as the user desire 
coins = [1,2,5,10]
print("The coin denominations to be considered are: ", coins)
l = len(coins) 
value = 44
print("The value to be made: ", value)
print("Minimum coins required is: ",minimumCoins(coins, l, value)) 

Output:

Test case 1:

The coin denominations to be considered are: [1, 2, 5, 10]
The value to be made: 44
Minimum coins required is: 6

Test case 2:

The coin denominations to be considered are: [1, 5, 10]
The value to be made: 12
Minimum coins required is: 3