Find minimum number of coins that make a given value | A Naive recursive python program to find minimum of coins to make a given change V ; m is size of coins array ( number of different coins ) ; base case ; Initialize result ; Try every coin that has smaller value than V ; Check for INT_MAX to avoid overflow and see if result can minimized ; Driver program to test above function
import sys NEW_LINE def minCoins ( coins , m , V ) : NEW_LINE INDENT if ( V == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT res = sys . maxsize NEW_LINE for i in range ( 0 , m ) : NEW_LINE INDENT if ( coins [ i ] <= V ) : NEW_LINE INDENT sub_res = minCoins ( coins , m , V - coins [ i ] ) NEW_LINE if ( sub_res != sys . maxsize and sub_res + 1 < res ) : NEW_LINE INDENT res = sub_res + 1 NEW_LINE DEDENT DEDENT DEDENT return res NEW_LINE DEDENT coins = [ 9 , 6 , 5 , 1 ] NEW_LINE m = len ( coins ) NEW_LINE V = 11 NEW_LINE print ( " Minimum ▁ coins ▁ required ▁ is " , minCoins ( coins , m , V ) ) NEW_LINE