C++ 代码

/*
完全背包问题 每种物品可用无限次
背包的总体积V：凑成面值为m的货币
物品的种类N: n种面值的货币
每种物品的体积v: 每种物品的价值
状态表示：f[i][j]  从前i个物品中选，且总体积恰好为j的所有选法集合的方案数
状态计算：f[i][j]=f[i-1][j]+f[i][j-v]
*/
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 3010;
long long  f[N];
int main()
{
    int n, m;
    cin >> n >> m;
    f[0] = 1;  //f[0][0]=1  啥都不选也是一种方案
    for (int i = 0; i < n; i++)
    {
        int v;
        cin >> v;
        for (int j = v; j <= m; j++)
            f[j] += f[j - v];
    }
    cout << f[m] << endl;
    return 0;
}