完全背包

背包系列问题 - 图1%2Cf0%3D0%0A#card=math&code=f_i%3D%5Cmax%5Climits%7Bj%5Cin%20S%7D%28f_%7Bi-w_j%7D%2Bv_j%29%2Cf_0%3D0%0A&id=HJAsp)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 10010, M = 100010;
  4. int n, m, w[N], v[N], dp[M];
  5. int main()
  6. {
  7.     cin >> m >> n;
  8.     for (int i = 1; i <= n; ++i)
  9.         cin >> w[i] >> v[i];
  10.     for (int j = 0; j <= m; ++j)
  11.         for (int i = 1; i <= n; ++i)
  12.             if (j >= w[i]) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
  13.     cout << dp[m] << endl;
  14.     return 0;
  15. }

当然，交换顺序也是可以的：

for (int i = 1; i <= n; ++i)
    for (int j = w[i]; j <= m; ++j)
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

01背包

背包系列问题 - 图2%20%3D%20%5Cmax%5Cleft%5C%7Bf(i-1%2C%20j)%2C%20f(i-1%2C%20j-w_i)%20%2B%20v_i%5Cright%5C%7D%0A#card=math&code=f%28i%2Cj%29%20%3D%20%5Cmax%5Cleft%5C%7Bf%28i-1%2C%20j%29%2C%20f%28i-1%2C%20j-w_i%29%20%2B%20v_i%5Cright%5C%7D%0A&id=wQO61)

for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= m; ++j) {
            dp[i][j] = dp[i - 1][j];
            if (j >= w[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
        }

我们可以滚动一下数组，压缩空间。

for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= m; ++j) {
            dp[i % 2][j] = dp[(i - 1) % 2][j];
            if (j >= w[i]) dp[i % 2][j] = max(dp[i % 2][j], dp[(i - 1) % 2][j - w[i]] + v[i]);
        }

我们也可以将其压到一维，但是枚举 j 时必须倒序，避免状态被覆盖（画个表就会发现，不倒序的话，直接就变成01背包了）

for (int i = 1; i <= n; ++i)
        for (int j = m; j >= w[i]; j--)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

多重背包

将其当成01背包写就太花时间了，我们需要对物品进行二进制拆分，将复杂度从线性降到对数。

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 40010;
int n, m, w[N], v[N], dp[M];
void divide(int ww, int vv, int num) {
    for (int i = 1; i <= num; i *= 2)
        w[++n] = ww * i, v[n] = vv * i, num -= i;
    if (num > 0)
        w[++n] = ww * num, v[n] = vv * num;
}
int main()
{
    //读入
    int cnt;
    cin >> cnt >> m;
    for (int i = 1; i <= cnt; ++i) {
        int ww, vv, num;
        cin >> vv >> ww >> num;
        divide(ww, vv, num);
    }
    //DP
    for (int i = 1; i <= n; ++i)
        for (int j = m; j >= w[i]; j--)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    cout << dp[m] << endl;
    return 0;
}

这个二进制拆分其实还可以用单调队列啥的进一步优化，我不太会，略。

二维费用背包

背包既有重量的限制，又有费用的限制。
和01背包类似，有这样的转移方程：

背包系列问题 - 图3%20%3D%20%5Cmax%5Cleft%5C%7Bf(i-1%2Cj%2Ck)%2C%20f(i-1%2Cj-w_i%2Ck-z_i)%20%2B%20v_i%5Cright%5C%7D%0A#card=math&code=f%28i%2Cj%2Ck%29%20%3D%20%5Cmax%5Cleft%5C%7Bf%28i-1%2Cj%2Ck%29%2C%20f%28i-1%2Cj-w_i%2Ck-z_i%29%20%2B%20v_i%5Cright%5C%7D%0A&id=J0av7)

同样的，我们可以压掉第一层（记得倒序）。

混合背包

有的物品只有一件，有的有多件，有的可以无限拿。
先将有多件的拆分，然后就变成了01+完全的问题，我们可以采取这样的策略：当前物品仅有一件时倒序，无穷件时顺序。

分组背包

在01的基础上面，加上了组的限制：每个组里面有若干个物品，只能选一个。
类似的转移方程，同样可以压进一维。

背包系列问题 - 图4%3D%5Cmax%7Bk%5Cin%20G_i%7D%5Cleft%5C%7Bf(i-1%2Cj)%2C%20f(i-1%2Cj-w_k)%2Bv_k%5Cright%5C%7D%0A#card=math&code=f%28i%2Cj%29%3D%5Cmax%7Bk%5Cin%20G_i%7D%5Cleft%5C%7Bf%28i-1%2Cj%29%2C%20f%28i-1%2Cj-w_k%29%2Bv_k%5Cright%5C%7D%0A&id=MeUMu)

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, zu;
vector<int> a[N];
int w[N], v[N], dp[N];
int main()
{
    cin >> m >> n;
    for (int i = 1; i <= n; ++i) {
        int k;
        cin >> w[i] >> v[i] >> k;
        a[k].push_back(i);
        zu = max(zu, k);
    }
    for (int k = 1; k <= zu; ++k)
        for (int j = m; j >= 0; j--)
            for (int p : a[k])
                if (j >= w[p]) dp[j] = max(dp[j], dp[j - w[p]] + v[p]);
    cout << dp[m] << endl;
    return 0;
}

树形背包

注：分组背包是树形背包的一种特殊形式。
在 01 背包的基础上，一些物品形成了依赖关系：只有选了某个，才能选另外一个。（如果有的物品没有依赖关系，可以人为添一个重量为 0 的虚拟物品）。
我们建树的时候，倘若 v 依赖 u，那么令 v 成为 u 的一个子节点。那显然的，倘若一个物品 x 选不了，那么以其为根的整个子树都选不了。 我们不妨进行一次 DFS 序，那么：

  1. 倘若选，那么就变成了 DFS 序下一个的子问题
  2. 不选，一整个子树都不能选，直接跳进管辖区间外的下一个的子问题

记 背包系列问题 - 图5#card=math&code=f%28i%2Cj%29&id=d13qE) 为从 i 到 n 的物品，容量为 j 的背包能装的价值，令 i 在DFS序里面管辖的区间为 背包系列问题 - 图6，那么有方程

背包系列问题 - 图7%3D%5Cmax%5C%7Bf(r_i%2B1%2C%20j)%2C%20f(i%2B1%2C%20j-w_i)%2Bv_i%0A#card=math&code=f%28i%2Cj%29%3D%5Cmax%5C%7Bf%28r_i%2B1%2C%20j%29%2C%20f%28i%2B1%2C%20j-w_i%29%2Bv_i%0A&id=sea8j)

（注：我上面所说的物品的标号，都是在新的DFS序意义下面标的序号，不是原来的）

#include<bits/stdc++.h>
using namespace std;
const int N = 310;
int n, m, v[N];
//Tree
vector<int> e[N];
int tot, id[N], R[N];
int Val[N];
void dfs(int x) {
    id[x] = ++tot;
    Val[id[x]] = v[x];
    for (auto y : e[x]) dfs(y);
    R[id[x]] = tot;
}
int dp[N][N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        int k;
        scanf("%d%d", &k, &v[i]);
        e[k].push_back(i);
    }
    dfs(0);
    for (int i = tot; i > 0; --i)
        for (int j = 0; j <= m; ++j)
            dp[i][j] = max(dp[R[i] + 1][j], dp[i + 1][j - 1] + Val[i]);
    printf("%d", dp[1][m]);
    return 0;
}