题解 P1474 【货币系统 Money Systems】
ShineEternal
2018-07-06 14:26:38
铺垫：对于一个给定了背包容量，物品费用，物品间相互的关系(分组、依赖等)的背包问题，除了再给定每个物品的价值后求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。
对于这类改变问法的问题，一般只需将状态转移方程中的max改成sum即可
事实上，这样做可行的原因在于状态转移方程已经考察了所有可能的背包组成方案
**by 一本通**
不知道以前的题解有没有，但我直接把我知道的**两种**给大家说一下。
方法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<cstdio>
using namespace std;
int a[10001];
int n,m;
long long f[10001];//注意用long long
int main()
{
scanf("%d%d",&n,&m);//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]];
}
}
}
printf("%lld",f[m]);//f[m]为最优解
return 0;
}
```
方法2：
```
//设f[j]表示面值为j的总方案数，如果f[j-a[i]]!=0,则f[j]=f[j]+f[j-a[i]],1<=i<=n,a[i]<=j<=m.
#include<cstdio>
using namespace std;
int a[10001];
long long f[10001];
int main()
{
int n,m;
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=a[i];j<=m;j++)
{
f[j]+=f[j-a[i]];
}
}
printf("%lld\n",f[m]);
return 0;
}
```
希望大家能接受
求过