In the UK, there are pounds £ and pence p, and there are eight types of coins in circulation:
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
It is possible to make £ 2 by the following method.
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many ways can I make £ 2 with these coins? http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2031
You can use it recursively. I understand.
def count_methods(target, coins):
if len(coins) == 0:
return 1
else:
s = 0
c = coins[0]
q = (target // c) + 1
for i in range(0,q):
s += count_methods(target - c * i, coins[1:])
return s
def main():
TARGET = 200
COINS = [200,100, 50, 20, 10, 5, 2]
print count_methods(TARGET,COINS)
main()
Recommended Posts