最基础01/完全背包

给定 个正整数 从中取出若干个数，使它们的和为 M，求有多少种选择方案。

因为每个数只能用一次，所以是0|1背包。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 110;
int f[N][11100];
int a[N];
int main(){
    //std::ios::sync_with_stdio(false);
    //std::cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    f[0][0] = 1;
    for (int i = 1; i <= n; i ++ ) {
       for (int j = 0; j <= m; j ++ ) {//j必须从0开始，初始化简单，而且符合定义
            f[i][j] = f[i - 1][j]; //不选
            if(a[i] <= j) f[i][j] += f[i - 1][j - a[i]];//能选的前提下选
       }
    }
    cout << f[n][m] << '\n';
    return 0;
}

因为阶段i都是由阶段i-1更新而来，0/1的经典优化——倒叙循环。保证用i-1更新i阶段

将“阶段”隐藏起来了，f[i]表示总和为i

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 11000;
int f[N];
int a[N];
int main(){
    //std::ios::sync_with_stdio(false);
    //std::cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    f[0] = 1;
    for (int i = 1; i <= n; i ++ ) {
       for (int j = m; j >= a[i]; j -- ) {
            f[j] += f[j - a[i]];
       }
    }
    cout << f[m] << '\n';
    return 0;
}

---

 从1到n可以取无数次，112和211是一种方案，完全背包

完全背包正序。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 11000;
const int mod = 1e9 + 7;
int f[N];
int main(){
    //std::ios::sync_with_stdio(false);
    //std::cin.tie(nullptr);
    int n;
    cin >> n;
    f[0] = 1;
    for (int i = 1; i <= n; i ++ ) {
       for (int j = i; j <= n; j ++ ) {
            f[j] = (f[j] + f[j - i]) % mod;
       }
    }
    cout << f[n] << '\n';
    return 0;
}