分析
注意区分完全背包和01背包的枚举区别。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e4 + 10;
int n,m,w[30];
LL f[N]; //凑成n元的方案数
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=0;i<n;i++) cin>>w[i];
f[0]=1;
for(int i=0;i<n;i++)
{
for(int j=w[i];j<=m;j++) //从当前钱数开始枚举
{
f[j]+=f[j-w[i]];
}
}
cout<<f[m];
return 0;
}