一个程序，可以使用任意数量的硬币计算出2.50英镑的所有不同方式

Question

2 fiddy

可以通过以下方式赚取 2.50 英镑：

1×£1 + 2×50p + 2×20p + 1×5p + 1×2p + 3×1p

编写一个程序，找出使用任意数量的硬币可以赚取2.50英镑的所有不同方式。

有没有更简单的方法可以在下面完成所有这些操作？

coins = [100,50,20,10,5,2,1]
number_of_coins = int(input("How many coins do you have: "))
num_of_ways = []
for i in range(3):
for j in range(6):
for k in range(13):
for l in range(26):
for m in range(51):
for n in range(126):
for o in range(251):
possible = [i*coins[0],j*coins[1],k*coins[2],l*coins[3],m*coins[4],n*coins[5],o*coins[6]]
if sum(possible) == 250 and i+j+k+l+m+n+o == number_of_coins:
num_of_ways.append([i,j,k,l,m,n,o])
rd = tuple(num_of_ways) #Remove Duplicates
for a in rd:
print(f'{rd[a][0]}×£1 + {rd[a][1]}×50p + {rd[a][2]}×20p + {rd[a][3]}×10p + {rd[a][4]}×5p + {rd[a][5]}×2p + {rd[a][6]}×1p')

Answer 1

使用递归。

提示：你可以使用0、1或2个100便士硬币(你如何确定可以使用多少个？(;无论你使用多少个这些硬币，你都需要使用面额[50,20,10,5,2,1]的硬币来弥补剩余的总和(你如何计算这个？((你如何从最初的coins列表中确定这一点？(。您的基本情况是没有可供使用的coins，也没有可供生产的金额;您可以完全以一种方式执行此操作(一个空的硬币列表(。唯一真正棘手的部分是组合所有递归调用的结果：对于递归的每个结果，您需要考虑当前调用中适当数量的硬币，然后整理您所做的每个递归调用的结果。