[问题描述]
给你一个 n 种面值的货币系统, 求组成面值为 m 的货币有多少种方案.
[输入]
第一行输入两个正整数 n 和 m, 用空格隔开, 分别表示货币系统的面值种数和要组成的总面值.
以下 n 行, 每行输入一个正整数, 表示货币系统的面值.
[输出]
一行一个数, 表示组成目标面值的方案总数.
[输入输出样例]
money.in | money.out |
3 10 1 2 5 | 10 |
[数据范围]
对于 100% 的数据, n<=100,m<=10000.
乍眼一看:
背包问题的方案总数
对于一个给定了背包容量, 物品费用, 物品间相互关系 (分组, 依赖) 的背包问题, 除了再给定每个物品的价值后求可得到的最大值以外, 还可以得到装满背包或将背包装置某一容量的方案总数(这道题就是这样).
对于这类改变问法的问题, 一般只需要将转移方程中的 max 改成 sum 即可.
例如若每件物品均是 01 背包中的物品, 转移方程即为 f[i][v]=sum{f[i-1][v],f[i-1][v-w[i]]+c[i]}, 初始条件 f[0][0]=1;
事实上, 这样做可行的原因在于状态转移方程已经考虑了所有可能的背包组成方案.
对于这道 货币系统:
设 f[j]表示面值为 j 的最大方案数, 如果 f[j-k*a[i]]!=0, 则 f[j]=f[j]+f[j-k*a[i]], 当 1<=i<=n,m>=j>=a[i],1<=k<=j/a[i].
程序
- :
- #include<iostream>
- #include<cstdio>
- using namespace std;
- int a[10001],n,m;
- long long f[10005];// 注意 long long
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++)
- {
- scanf("%d",&a[i]);
- }
- f[0]=1;
- for(int i=1;i<=n;i++)
- for(int j=m;j>=a[i];j--)//f[j]表示面值为 j 的方案最优解.
- for(int k=1;k<=j/a[i];k++)
- f[j]+=f[j-k*a[i]];
- cout<<f[m];// 表示最优解.
- return 0;
- }
来源: https://www.cnblogs.com/FXY-180/p/9509429.html