问题描述
评测题目: 给定 m 种面值的硬币，每种面值的硬币有无限多个，它们的面值分别为C=[c[0], c[1], …, c[m-1]]，现用这些面值的硬币凑齐 n 元，求有多少种方法。如 n=3, m=4, c =[8, 3, 1, 2]，则有 3 种方法，分别为 {1, 1, 1}、{1, 2}、{3} 。
问题分析
给定一个金额n，假设有m种面值的硬币C=[c[0], c[1], …, c[m-1]]，现用这些面值的硬币凑齐 n 元，有求所有可能的组合数，就是求满足前面等值的系数X=[x[0], x[1], …, x[m-1]]的所有可能个数。
【思路1】 采用暴力枚举的方法，各个系数可能的取值分别为x[0] = {0, 1, ..., n/c[0]}, ……, x[m-1] = {0, 1, ..., n/c[m-1]}。这适用于硬币种类数较小的问题，但是复杂度很高O(n/c[0]×…×n/c[m-1])）
【思路2】 定义num[i,j]为用前i种硬币（所有硬币）凑齐j元的所有组合数，那么题目的问题实际上就是求num[m,n]。设k为使用面值为c[m-1]的硬币凑齐n元所允许的最大个数，那么所有可能的组合数可以表示为c[m-1]的个数j从0个一直变到k个的时候满足n-j*c[m-1]的所有组合数之和。也就是说，我们通过固定最后一种面值的硬币数量，来求取剩余面值硬币凑齐余额的组合数。因此，对num[m,n]，有由此式可以看出此表达式可用递归的方法，逐步缩减问题的规模，然后求解。下面讨论递归的初始值，即num[i,0]的情况。显然如果n=0，那么无论有前多少种来组合0，只有一种可能，就是各个系数都等于0，所以对每一个i，都有num[i][0] = 1。
Python代码
# 评测题目: 给定 m 种面值的硬币，每种面值的硬币有无限多个，
# 它们的面值分别为 C=[c[0], c[1], …, c[m-1]]，
# 现用这些面值的硬币凑齐 n 元，求有多少种方法。
# 如 n=3, m=4, c =[8, 3, 1, 2]，则有 3 种方法，分别为 {1, 1, 1}、{1, 2}、{3} 。
import numpy as np
def combination(c,n,m):
num = np.zeros((m + 1, n + 1)) # num[i,j]为用前i种硬币（所有硬币）凑齐j元的所有组合数
for i in range(m+1):
num[i][0] = 1
for i in range(1,m+1):
for j in range(1,n+1):
for k in range(j//C[i-1]+1):
num[i][j] += num[i-1][j-k*C[i-1]]
return num[m][n]
C = np.array([8,1,2,3])
N = 3
M = 4
print('%d' %(combination(C,N,M)))
参考文献
[1] https://www.cnblogs.com/python27/archive/2013/09/05/3303721.html
