8595 钱币组合方法数的问题 时间限制:300MS 内存限制:1000K 提交次数:43 通过次数:17 题型: 编程题 语言: 无限制 Description 设有 n 种不同的钱币各若干，可用这 n 种钱币产生许多不同的面值。 如给定面值 7 分，有 1 分 3 张，2 分 3 张，5 分 1 张，能组成给定面值 7 分的方法有如下 4 种： 3 个 1 分+2 个 2 分； 1 个 1 分+3 个 2 分； 2 个 1 分+1 个 5 分； 1 个 2 分+1 个 5 分。 你的编程任务：给定面值 m，和 n 种不同钱币及其张数，求给定面值 m 能有多少种不同的构成方法数。 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,0<=j<=m。(若 j<0,定义 d[i,j]=0) d[i,0] = 1, if 1<=i<=n d[1,j] = 1, if j%v[1]=0 && j/v[1]<=k[1]; d[1,j] = 0, if j%v[1]!=0 || j/v[1]>k[1] || j<0; if i>1 && j < v[i] d[i,j] = d[i-1,j] if i>1 && v[i] <= j < 2*v[i] d[i,j] = d[i-1,j] + d[i-1,j-v[i]] if i>1 && 2*v[i] <= j < 3*v[i] d[i,j] = d[i-1,j] + d[i-1,j-v[i]] + d[i-1,j-2*v[i]] ...... if i>1 && k[i]*v[i] <= j <= m d[i,j] = d[i-1,j] + d[i-1,j-1*v[i]] + d[i-1,j-2*v[i]] + ... + d[i-1,j-k[i]*v[i]] 最后 d[n,m]为原问题所求。 当然由于这里的 d 数组 d[i,j]只与 d[i-1,...]有关，也完全可以用一维数组 d[1...m]来实现。 Provider zhengchan 

Source Code #include #include using namespace std; int method=0; int count(int money,int n,int a[],int b[]) { int i,j,k; //k 表示钱币的张数 if(money/a[n-1]=(j/a[n-1])) { if (j<0) return 0; method++; return 0; } else return 0; for(i=0;i<=k;i++) { j=money; j=j-i*a[n-1]; if(j<0) return 0; else if(j==0) {method++;return 0;} else count(j,n-1,a,b); } return 0; } } 

int main() { int value[10],pieces[10]; int n,m; int i; cin >> n; for(i=0;i> value[i]; //表示每种钱币的面值 for(i=0;i> pieces[i]; //表示每种钱币的张数 cin >> m; //表示给定的面值 m count(m,n,value,pieces); cout<