考点:DP,背包问题
二维写法:
#include <iostream>
using namespace std;
const int N = 30,M = 10010;
long long f[N][M];
int main()
{
int n,m;
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;
const int N = 30,M = 10010;
long long f[M];
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 = v; j <= m; j ++ )
{
f[j] += f[j - v];
}
}
cout << f[m] << endl;
return 0;
}