开发工具:
文件大小: 1kb
下载次数: 0
上传时间: 2012-11-01
详细说明：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]来实现。
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
