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;
}