首先,这是一道典型的背包模板题(可以从比赛名称看出来(逃)

背包是线性dp中一类较为重要而又特殊的模型，大多都是有着固定的套路在里面.主要分为01背包,多重背包,完全背包，这三类的区别十分明显，01背包是单个物品只能取一次，多重背包是单个物品可以取有限次，而完全背包则可以取无限次，根据取的次数不同，三种背包的核心代码也会稍有不同.除此之外就是这三类的各种混搭变形与优化，难度都不是特别大，只要可以保证足够的刷题量就可以将这个模块吃下.所以对于还不熟悉这个套路的人,蒟蒻在这里列出来一个题单(仅供参考

简单题&经典题

  • luogu P1048 采药
  • luogu P1060 开心的金明
  • luogu P1064 金明的预算方案
    (这三道都是往年的普及组测试题,比较简单,但都很基础

进阶题

  • luogu P1273 & 本书0x54中的选课 都是将树形dp与背包相结合
  • luogu P1776 宝物筛选_NOI导刊2010提高（02）是需要单调队列优化的多重背包
  • luogu P1941 飞扬的小鸟 属于背包混搭加一点特判

下面我们进入正题QAQ

在知道解题所用方法时,我们就可以再通过题面很轻易的看出这是个01背包(因为每个物品只能使用一次

01背包问题的一般模型如下（或者说是所有01背包的潜台词？？：

给定n个物品，其中第i个物品体积为vi，价值为wi，有一个容量为M的背包，要求将一些物品放入背包内，保证在总体积不超过M的情况下使得物品的总价值最大qaq

一般情况下,01背包的模板都是如下代码所示:

for(int i=1;i<=m;i++){
        for(int j=n;j>=tim[i];j--){
//内部为你需要执行的操作
        }
    }

请注意，以上代码的第二重for循环我们用了倒序，这个属于01背包一大难点，具体证明请自行翻书（逃

至于本题，很明显可以看出N是n个物品，M为背包容积，由于题目要求的是和为j是的方案数，所以我们很容易得出状态转移方程：f[j] += f[j-a[i]];

此时我们回头看题，题目要求中（1<N<100）和(1<M<10000)
而01背包的复杂度为O（nm），可以轻松跑过，于是我们就可以开开心心的把01背包模板打上去了qaq

code

#include <bits/stdc++.h>
#define ll long long

const int N = 110;
using namespace std;

ll n, m;
int a[N], f[N];

int main () {
    cin >> n >> m;
    for (register int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    f[0] = 1;
    for (register int i = 1; i <= n; i++) {
        for (register int j = m; j >= a[i]; j--) {
            f[j] += f[j-a[i]];
        }
    }
    cout << f[m] << endl;
    return 0;
}

最后，给挣扎在背包苦海中的大佬们一个福利
https://www.kancloud.cn/kancloud/pack/70124 （由于没有超链接这个功能，只能将网址发出来了，这是一位真·巨佬写的背包九讲，请各位放心食用）