python/TangDou/XiTi/1302.cpp

#include <bits/stdc++.h>

using namespace std;

/*
http://oj.521ma.cn/problem.php?id=1302

视频讲解
https://www.bilibili.com/video/av88194897/

感想：原来只要掌握基本背包问题，一些变换的题型也可以解决。

状态转移方程：
 i:i件物品
 j:在j这个大的空间内

 dp  状态表示  f(i,j)  --->集合---->从前i个数中选且和为m的所有选法
                      --->属性---->方案数，即数量 count

 dp  状态计算  第i个数选还是不选   ----> 不选-->f(i-1,j)
                               ----> 选 -->f(i-1,j-a[i])

 把选与不选的总个数加在一起，就是最终想要的结果
 f(i,j)=f(i-1,j)+f(i-1,j-ai) 二维转一维---->f(j)=f(j)+f(j-ai)
 */
const int N = 1001;
int a[N], f[N];
int n, m;


int main() {
    //输入+输出重定向
    freopen("../1302.txt", "r", stdin);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];

    //初始化 因为如果和为0，那也就是什么都不放，那就是1种方案，所以初始化f[0]=1,
    f[0] = 1;

    //遍历每一个数字
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= a[i]; j--) //和01背包一样，需要倒序
            f[j] = f[j] + f[j - a[i]];  //求count问题

    cout << f[m] << endl; //输出结果
    //关闭文件
    fclose(stdin);
    return 0;
}