SHARE
TWEET

Untitled

a guest Jun 16th, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # given an amount and coin denominations,
  2. # compute the number of ways to make amount with coins of the given denoms
  3. # 4, [1,2,3] -> 4
  4. def ways_to_make(amount, denoms):
  5.     # ways to make 4
  6.     # ~ ways(4 - 3) + ways(4 - 2) + ways(4 - 1) ~
  7.  
  8.     # ways(1, largest=1) + ways(2, largest=1)
  9.  
  10.     # dim 1: amount
  11.     # dim 2: largest denomination used
  12.  
  13.     # 1: 1
  14.     # 2: 11, 2
  15.     # 3: 111, 12, 3
  16.     # 4:
  17.  
  18.     #              amount
  19.     #
  20.     #            0 1 2 3 4
  21.     #          1 1 1 1 1 1
  22.     # largest  2 1 1 2 2 3
  23.     #          3 1 1 2 3 4
  24.     #          4 1 1 2 3 5
  25.  
  26.     # ways(4, 3) =
  27.     #   # use 3
  28.     #   ways(4 - 3, 3) = 1
  29.     #   # use 2
  30.     #   ways(4 - 2, 2) = 2
  31.     #   # use 1
  32.     #   ways(4 - 1, 1) = 1
  33.  
  34.     denoms.sort()
  35.  
  36.     # there's one way to make 0, no matter what denominations we use
  37.     ways = [[1] * len(denoms)]
  38.  
  39.     # determine how many ways there are to make current_amount (using only
  40.     # denominations or size `row` or smaller)
  41.     for current_amount in range(1, amount + 1):
  42.  
  43.         column = []
  44.         for row in denoms:
  45.             count = 0
  46.  
  47.             # for each denomination less than or equal to the current row, add
  48.             # the number of ways to make `current_amount - denom`.
  49.             for denom_ix, denom in enumerate(denoms):
  50.                 # this and all larger denominations are too big
  51.                 if denom > row or denom > current_amount:
  52.                     break
  53.                 else:
  54.                     count += ways[current_amount - denom][denom_ix]
  55.  
  56.             column.append(count)
  57.  
  58.         ways.append(column)
  59.  
  60.     return ways[amount][-1]
  61.  
  62. if __name__ == '__main__':
  63.     print(ways_to_make(0, [1]))
  64.     print(ways_to_make(0, [1,2,3]))
  65.     print(ways_to_make(4, [1,2,3]))
  66.     print(ways_to_make(4, [1,2,3,7,8,9,1000]))
  67.     print(ways_to_make(4, [1,2,3,4]))
  68.     print(ways_to_make(4, list(range(1,100000))))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top