$DP$

状态定义: $f[i][j]$
集合：从前$i$件物品中选(每件物品都可以选无限件)，刚好凑出价值$j$的方案数
状态计算：$f[i][j]$ += $f[i - 1][j - k × v]$(选$k$个第$i$件物品)

例题

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 20, M = 3010;
long long f[N][M];
int main()
{
    int n, m; cin >> n >> m;
    for (int i = 0; i <= n; i ++) f[i][0] = 1;
    for (int i = 1; i <= n; i ++)
    {
        int v; cin >> v;
        for (int j = 1; j <= m; j ++)  // 枚举体积
            for (int k = 0; k * v <= j; k ++)  // 枚举可以由选几张当前面值转移过去
                f[i][j] += f[i - 1][j - k * v];
    }
    cout << f[n][m];
    return 0;
}

滚动数组优化

#include<bits/stdc++.h>
using namespace std;
const int N = 3010;
long long f[N];
int main()
{
    int n, m; cin >> n >> m;
    f[0] = 1;
    for (int i = 1; i <= n; i ++)
    {    
        int v; cin >> v;
        for (int j = 1; j <= m; j ++)
            if (j >= v)f[j] = f[j] + f[j - v];
    }
    cout << f[m];
    return 0;
}