• API
• FAQ
• Tools
• Archive
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.

Top