“货币系统”解题思路
发布时间
阅读量：
阅读量
题目描述
母牛们创建了自己的政府，并且同时建立了独立的货币体系。对于币制的价值充满好奇的是这些聪明的生命体。任何有效的币制都是由一系列固定面值硬币组成的系列——这些硬币既可以是单向递增也可以是多向递增的形式排列出来。
为了深入研究这个问题，请考虑编写一个程序来计算给定的钱包组合能够达到特定金额的不同方式的数量。
输入格式：
此段代码中包含两个整数n, v, 其中变量v(取值范围为1到25)代表货币系统的不同币种数量, n是我们要计算的最大金额(其取值范围为1到10000)。从第二行到第(v+1)行分别给出可用的各种货币面额。
输出格式：
输出方案总数。
样例输入：
3 10
1
2
5样例输出 ：
10OK，审完题，都有所收获吧！
这本质上是一道组合优化问题, 同样也可以视为一种完全背包问题, 因此我们可以采用多种方法来解决
FIRST 组合问题 代码
#include<iostream>
using namespace std;
int a[105];
long long f[1005];//注意要用long long
int main(){//f[j]表示面值为j的总方案数
int n,m;//n种面值的货币，组成面值为m
cin >> n>>m;
for(int i = 1;i<= n;i++) cin >> a[i];
f[0] = 1;//如果腾出的背包容量刚好剩余为0，方案数应为1，保证了f[j-a[i]]
for(int i = 1;i <= n;i++){
for(int j = a[i];j<=m ; j++){//f[j]表示面值为j的总方案数
f[j] = f[j] + f[j-a[i]];
}
}
cout<<f[m];
return 0;
}大家可以对照着注释理解一下！
SECOND 完全背包问题 代码：
#include<iostream>
using namespace std;
int m,n,z[101];
int f[101][101];
int main(){
cin >> n >> m;
for(int i = 1;i <= n;i++){
cin >>z[i];
f[i][0] = 1;
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
if(j >= z[i]) f[i][j] = f[i-1][j] + f[i][j-z[i]];
else f[i][j] = f[i-1][j];
}
}
cout<<f[n][m];
return 0;
}这个概念可能较为抽象难以直接理解，在运用二维数组的思想时会面临相较于第一种方法更为复杂的挑战，并且其空间复杂度同样较高。因此建议各位根据个人需求选择相应的代码实现。
全部评论 (0)
还没有任何评论哟~