Problem Solving

After you have worked out an algorithm for solving a problem, write a program that implements your algorithm.

Making Change

Making change is an important activity that occupies a lot of people's time. Some people have difficulty figuring out how to make their coins add up to the right amount; while others have problems figuring out how to make a given sum from what they have in their pocket.

You are given an int, the amount of money to make change for, and a list of ints, the denominations of coins you have available (i.e., 25 for a quarter, 10 for a dime, etc.). Using the coins given, return the fewest number of coins needed to represent that amount of money. For example, 10 cents can be represented by the following coins:

• one dime
• two nickels
• one nickel, five pennies
• ten pennies

Your function should return 1 since one dime requires the fewest coins. Your function should return 0 if it cannot make change for the given amount with the coins given.

You can assume there are an "infinite" number of any given coin (i.e., you will not run out of any kind of coins while making change).

Here is the function declaration in Python:

def makeChange (amount, coins):
   """
   return an int, the number of coins needed, to represent the 
   given amount, an int, using the given coins, a list of ints
   """

Examples

1. amount = 76
   coins = [25, 10, 5, 1]
   
   Returns: 4
   

   The fewest coins needed is 3 quarters and 1 penny.

2. amount = 76
   coins = [10, 5, 1]
   
   Returns: 9
   

   Since no quarters are available, the fewest coins needed is 7 dimes, 1 nickel, and 1 penny.

3. amount = 4
   coins = [25, 10, 5]
   
   Returns: 0
   

   Since there are no pennies, there is no way to represent this amount of change.