Solution: Counting Money
This review provides a detailed analysis of the different ways to solve the counting money challenge.
We'll cover the following...
Solution: greedy approach
Caution!!
This is not the most optimized solution. It is only to give you an idea of how the greedy algorithm works.
def find_min_coins(v, coins_available):"""This function finds the minimum number of coins:param v: Total amount:param coins_available: Coins available in the machine:return: A list of total coins"""# Initialize resultresult = []n = len(coins_available)# Traverse through all available coinsfor i in reversed(range(n)):while v >= coins_available[i]:v -= coins_available[i]result.append(coins_available[i])return result# Main program to test the above codeif __name__ == "__main__":coins_available = [1, 5, 10, 25] # The available coins are in increasing orderprint(find_min_coins(19, coins_available))
Explanation
The simple greedy idea is to start from the largest possible coin available and keep adding coins, ...