fork download
copy 
  1. # coins:            A list with the values of the coins we're using
  2. # myCoins:          Index into the coins list of the current coin
  3. # amountNeeded:     Our current goal for number of cents
  4. # coinsUsed:        A list of the number of each coin used thus far. Mostly
  5. #                   for sanity checking and printing all of the combinations.
  6. # check:            If this is true, sanity checking is performed.
  7. def combinationsOfCoinsRec( coins, myCoin, amountNeeded, coinsUsed, check ):
  8.     if amountNeeded == 0:
  9.         # We've reached our desired value exactly, so return that this
  10.         # combination is valid.
  11.  
  12.         # If check is true, perform sanity checking first and print coinsUsed
  13.         if check:
  14.             coinVal = 0
  15.             for i in range(len(coinsUsed)):
  16.                 coinVal += coinsUsed[i] * coins[i]
  17.             assert(coinVal == 100)
  18.  
  19.             print "{0} = {1}".format(coinsUsed, coinVal)
  20.  
  21.         return 1
  22.  
  23.     if amountNeeded < 0 or myCoin >= len(coins):
  24.         # We don't have any more coin types or we went over our desired value,
  25.         # so this is not a valid combination
  26.         return 0
  27.  
  28.     # If we've gotten this far, we haven't met our desired amount yet, so
  29.     # let's see how many combinations we can find that use various amounts
  30.     # of our coin.
  31.     combinations = 0
  32.  
  33.     # This is the maximum number of our coin that it makes sense to try
  34.     maxNumOurCoin = amountNeeded / coins[myCoin]
  35.  
  36.     # Note: we add 1 to the range because the range function gives us all
  37.     # values from 0 up to the value we specify, but not including it.
  38.     for numCoins in range( maxNumOurCoin + 1 ):
  39.         newNeeded = amountNeeded - (coins[myCoin] * numCoins)
  40.  
  41.         # Append the number of our coin we used for sanity checking.
  42.         newCoinsUsed = list(coinsUsed)
  43.         newCoinsUsed.append(numCoins)
  44.  
  45.         # Add the number of combinations of other coins we haven't used yet
  46.         # that bring us to the desired value
  47.         combinations += combinationsOfCoinsRec( coins, myCoin + 1, newNeeded, newCoinsUsed, check )
  48.  
  49.     return combinations
  50.  
  51. # Just a helper function that initializes all of the extra stuff for the
  52. # recursive function
  53. def combinationsOfCoins( coins, amountDesired, check = False ):
  54.     if amountDesired < 0:
  55.         raise RuntimeError("You can't desire a negative number of coins, silly!")
  56.  
  57.     return combinationsOfCoinsRec( coins, 0, amountDesired, [], check )
  58.  
  59. # Set up the coins we're going to use
  60. coinValues = [100, 50, 25, 10, 5, 1]
  61. desiredCents = 100
  62.  
  63. print combinationsOfCoins( coinValues, desiredCents )
Success #stdin #stdout 0.09s 8880KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
293
https://ideone.com/qTjCLP
language:
Python (cpython 2.7.16)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!