货币系统_(完全背包，方案数)

原题链接：1371. 货币系统 - AcWing题库

题意：给定不同面额的货币，每种货币任意选择，要求达到给定金额的货币的组合方案数

思路

完全背包

每种任选，不限次数，完全背包

状态表示

当前金额的方案数

状态计算

分类 到达当前金额，最后一次选的可以是所有可能货币，因此有 f[j] += f[j - w[i]]

实现

每次需要f[j]之前的数来计算f[j] 所以先遍历 背包 再遍历 当前重量

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
typedef long long LL;
 
const int N = 30, M = 1e4 + 10;
 
int a[N];
int v, n;
LL f[M];
 
 
int main()
{
    cin >> v >> n;
    
    for(int i = 1; i <= v; i ++)
        cin >> a[i];
        
    f[0] = 1;
    for(int i = 1; i <= v; i ++)
        for(int j = a[i]; j <= n; j ++)
        {
            f[j] += f[j - a[i]];
        }
        
    cout << f[n] << endl;
    
    return 0;
}