文件名称：8595 钱币组合方法数的问题
文件大小：1KB
文件格式：TXT
更新时间：2015-11-22 06:47:34
钱币组合
8595 钱币组合方法数的问题 时间限制:300MS 内存限制:1000K 提交次数:43 通过次数:17 题型: 编程题 语言: 无限制 Description Input 第1行有1个正整数n(1<=n<=10)，表示有n种不同的钱币。 第2行有n个数，分别表示每种钱币的面值v[1]...v[n](0<=v[i]<=100,1<=i<=n)。 第3行有n个数，分别表示每种钱币的张数k[1]...k[n](0<=k[i]<=100,1<=i<=n)。 第4行有1个数，表示给定的面值m (1<=m<=20000)。Output 计算出的给定面值的不同产生方法种数 Sample Input 3 1 2 5 3 3 1 7 Sample Output 4 Hint 给定的总面值m，n种钱币，每种钱币面值v[1...n],每种钱币的张数k[1...n]， 用一个二维数组d[i][1...m]记录用前i种钱币组成1...m面值产生的方法数。1<=i<=n。 初始，该数组全清零，然后逐个加入第i种面值的钱币（1<=i<=n），并修改影响到数组d的方法数。 设d[i,j]:表示前i种钱币组成面值j分的方法数，1<=i<=n,1<=j<=m。则： d[1,j] = 1, if j%v[1]=0 && j/v[1]<=k[i]; d[1,j] = 0, if j%v[1]!=0 || j/v[1]>k[i] || j<=0; d[i,j] = d[i-1,j], if i>1 && j < v[i] d[i,j] = d[i-1,j] + d[i-1,j-1*v[i]] + ... + d[i-1,j-k[i]*v[i]], if i>1 && v[i] <= j <= m 最后d[n,m]为原问题所求。 当然由于这里的d数组d[i,j]只与d[i-1,j]有关，完全可以用一维数组d[1...m]来实现。