ACM模版
描述
题解
取与不取？这个值得思考？是不是很像01背包啊，不过不同的地方是，01背包是求能容最大价值，而这里是求能凑够 M 的方法数，其实很相似的，甚至更简单吧！
由于数据很弱，这个题其实用 dfs 搜索一下也可以解决，没什么大不了的，很水的一道题。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN =
110;
const int MAXM =
1010;
int A[MAXN];
int dp[MAXM];
int main(
int argc,
const char * argv[])
{
int T;
cin >> T;
int N, M;
while (T--)
{
cin >> N >> M;
for (
int i =
1; i <= N; i++)
{
scanf(
"%d", A + i);
}
memset(dp,
0,
sizeof(dp));
dp[
0] =
1;
for (
int i =
1; i <= N; i++)
{
for (
int j = M; j >= A[i]; j--)
{
if (dp[j - A[i]])
{
dp[j] += dp[j - A[i]];
}
}
}
cout << dp[M] <<
'\n';
}
return 0;
}
