二维解法
完全背包问题,写出n^3级别的后对f[i][j]换元f[i][j-v]从而进行替换
得到f[i][j]=f[i-1][j]+f[i][j-v]
本题爆long long
#include<iostream>
using namespace std;
//本题爆long long
typedef long long LL;
const int N = 30,M=10010;
LL f[N][M];
int n,m;
int main()
{
cin>>n>>m;
f[0][0]=1;
for(int i=1;i<=n;i++)
{
int v;
cin>>v;
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
if(j>=v) f[i][j]+=f[i][j-v];
}
}
cout<<f[n][m]<<endl;
return 0;
}
一维算法
优化空间之后的做法
目前还不太能接受这咋做法,时间效率看起来优化不是很明显,先打好二维的基础
#include<iostream>
using namespace std;
//本题爆long long
typedef long long LL;
const int N = 30,M=10010;
LL f[M];
int n,m;
int main()
{
cin>>n>>m;
f[0]=1;
for(int i=1;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;
}