【acwing 寒假每日一题（入门组）】day15货币系统

题目来源：货币系统

题目描述

给定 V 种货币（单位：元），每种货币使用的次数不限。

不同种类的货币，面值可能是相同的。

现在，要你用这 V 种货币凑出 N 元钱，请问共有多少种不同的凑法。

输入格式
第一行包含两个整数 V 和 N。

接下来的若干行，将一共输出 V 个整数，每个整数表示一种货币的面值。

输出格式
输出一个整数，表示所求总方案数。

数据范围
1≤V≤25,
1≤N≤10000
答案保证在long long范围内。

输入样例：
3 10
1 2 5
输出样例：
10

思路

典型的完全背包问题，三个版本慢慢推进，思路看代码的详细注释

代码

朴素做法

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=30,M=10010;

int n,m;
int v[N];
LL f[N][M];

/*
    状态定义：f[i][j]表示用i种货币凑出面置j的方案的数量
    属性：数量
    状态转移(该怎么表示当前状态 或者是当前状态的集合可能怎么划分)：
        可以使用第i中货币使用的次数来划分
        使用0次、1次、、、n次 但是n必须满足 n*v[i]<=j 即不能大于需要我们凑的钱
        使用0次指的是，用前i-1个货币凑出面置j，按照我们定义就是f[i-1][j]
        使用1次指的是，用前i-1个货币凑出面置j-v[i]，按照我们定义就是f[i-1][j-v[i]]
        ...
        使用n次指的是，用前i-1个货币凑出面置j-n*v[i]，按照我们定义就是f[i-1][j-n*v[i]]
        
        f[i][j]=f[i-1][j]+f[i-1][j-v[i]+...+f[i-1][j-n*v[i]]
*/

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i];
    
    f[0][0]=1; //初始状态，0种货币凑出面置0，一种方案
    for(int i=1;i<=n;i++) //使用i种货币
        for(int j=0;j<=m;j++) //凑出面置j
            for(int k=0;k*v[i]<=j;k++) //使用第i种货币k次数
            {
                f[i][j]+=f[i-1][j-k*v[i]]; //累加方案数
            }
    cout<<f[n][m]<<endl; //结果就是 使用n种货币凑出面置m的方案数
    return 0;
}

转移方程优化

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=30,M=10010;

int n,m;
int v[N];
LL f[N][M];

/*
    状态定义：f[i][j]表示用i种货币凑出面置j的方案的数量
    属性：数量
    状态转移(该怎么表示当前状态 或者是当前状态的集合可能怎么划分)：
        可以使用第i中货币使用的次数来划分
        使用0次、1次、、、n次 但是n必须满足 n*v[i]<=j 即不能大于需要我们凑的钱
        使用0次指的是，用前i-1个货币凑出面置j，按照我们定义就是f[i-1][j]
        使用1次指的是，用前i-1个货币凑出面置j-v[i]，按照我们定义就是f[i-1][j-v[i]]
        ...
        使用n次指的是，用前i-1个货币凑出面置j-n*v[i]，按照我们定义就是f[i-1][j-n*v[i]]
        
        f[i][j]=f[i-1][j]+f[i-1][j-v[i]+...+f[i-1][j-n*v[i]]
        
        
        
        我们惊人的发现：
        f[i][j-v[i]]=f[i-1][j-v[i]]+f[i-1][j-2*v[i]]+...+f[i-1][j-n*v[i]]
        也就是说 f[i][j]=f[i-1][j]+f[i][j-v[i]]
*/

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i];
    
    f[0][0]=1; //初始状态，0种货币凑出面置0，一种方案
    for(int i=1;i<=n;i++) //使用i种货币
        for(int j=0;j<=m;j++) //凑出面置j
        {
            //下面是转移方程，但是需要j>=v[i] 不然肯定不成立
            f[i][j]=f[i-1][j];
            if(j>=v[i]) f[i][j]+=f[i][j-v[i]];
        }
    cout<<f[n][m]<<endl; //结果就是 使用n种货币凑出面置m的方案数
    return 0;
}

空间优化

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=30,M=10010;

int n,m;
int v[N];
LL f[M];

/*
    状态定义：f[i][j]表示用i种货币凑出面置j的方案的数量
    属性：数量
    状态转移(该怎么表示当前状态 或者是当前状态的集合可能怎么划分)：
        可以使用第i中货币使用的次数来划分
        使用0次、1次、、、n次 但是n必须满足 n*v[i]<=j 即不能大于需要我们凑的钱
        使用0次指的是，用前i-1个货币凑出面置j，按照我们定义就是f[i-1][j]
        使用1次指的是，用前i-1个货币凑出面置j-v[i]，按照我们定义就是f[i-1][j-v[i]]
        ...
        使用n次指的是，用前i-1个货币凑出面置j-n*v[i]，按照我们定义就是f[i-1][j-n*v[i]]
        
        f[i][j]=f[i-1][j]+f[i-1][j-v[i]+...+f[i-1][j-n*v[i]]
        
        
        
        我们惊人的发现：
        f[i][j-v[i]]=f[i-1][j-v[i]]+f[i-1][j-2*v[i]]+...+f[i-1][j-n*v[i]]
        也就是说 f[i][j]=f[i-1][j]+f[i][j-v[i]]
        
        
        接着我们对空间进行优化
         f[i][j]=f[i-1][j]+f[i][j-v[i]] 变为了f[j]=f[j]+f[j-v[i]]
         直接将前面一维删掉了，为什么可以这样呢？
         其实如果是f[i][j]=f[i][j]+f[i][j-v[i]]，我们肯定会直接删掉一维的，但是他是i-1
         其实是直接删掉也是不影响的，
         因为我们当前计算的是f[j],所以式子右边的f[j]肯定是之前的数据，
         而f[j-v[i]]比f[j]小，我们是从前往后计算的，那么这个f[j-v[i]]肯定是新的数据
*/

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i];
    
    f[0]=1; //初始状态，0种货币凑出面置0，一种方案
    for(int i=1;i<=n;i++) //使用i种货币
        for(int j=v[i];j<=m;j++) //凑出面置j
        {
            f[j]=f[j]+f[j-v[i]];
        }
    cout<<f[m]<<endl; //结果就是 使用n种货币凑出面置m的方案数
    return 0;
}