背包九讲封面

背包九讲：模型、状态转移与 C++ 模板¶

背包动态规划的核心不是记代码，而是回答三个问题：每件物品能选几次、不同物品之间有什么约束、状态记录什么信息。确定模型后，循环顺序通常就随之确定。

本文默认物品体积为 $v_i$、价值为 $w_i$，背包容量为 $V$。若无特别说明，dp[j] 表示容量不超过 $j$ 时的最大价值。

0. 一张表看懂循环顺序¶

类型	物品限制	容量循环	典型复杂度
01 背包	每件最多一次	从大到小	$O(NV)$
完全背包	每件无限次	从小到大	$O(NV)$
多重背包	每件最多 $s_i$ 次	二进制拆分后从大到小	$O(V\sum\log s_i)$
混合背包	三种数量限制并存	按物品类型决定	视拆分后物品数而定
二维费用	同时受两种容量约束	两维都从大到小	$O(NVW)$
分组背包	每组至多选一件	组 → 容量逆序 → 组内物品	$O(V\sum

一维优化后，01 背包必须逆序，避免同一物品在同一轮被重复使用；完全背包必须正序，主动允许当前物品重复转移。

1. 01 背包¶

模型¶

每件物品只有“选”或“不选”两种决策：

\[ f_{i,j}=\max(f_{i-1,j},\ f_{i-1,j-v_i}+w_i). \]

压缩第一维后，容量必须从大到小枚举。

C++ 模板¶

C++
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, V;
    cin >> n >> V;
    vector<int> dp(V + 1);
    for (int i = 0, v, w; i < n; ++i) {
        cin >> v >> w;
        for (int j = V; j >= v; --j) {
            dp[j] = max(dp[j], dp[j - v] + w);
        }
    }
    cout << dp[V] << '\n';
}

中文模板：AcWing 2. 01 背包问题
练习：洛谷 P1048 采药、洛谷 P2871 Charm Bracelet S

2. 完全背包¶

模型¶

每种物品可以选无限次。朴素转移会枚举件数，优化后得到：

\[ f_{i,j}=\max(f_{i-1,j},\ f_{i,j-v_i}+w_i). \]

第二项仍在当前物品层，因此一维数组中容量要从小到大枚举。

C++ 模板¶

C++
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, V;
    cin >> n >> V;
    vector<int> dp(V + 1);
    for (int i = 0, v, w; i < n; ++i) {
        cin >> v >> w;
        for (int j = v; j <= V; ++j) {
            dp[j] = max(dp[j], dp[j - v] + w);
        }
    }
    cout << dp[V] << '\n';
}

中文模板：AcWing 3. 完全背包问题
练习：洛谷 P1616 疯狂的采药、洛谷 P2722 总分

3. 多重背包¶

模型¶

第 $i$ 种物品最多选 $s_i$ 次。直接枚举件数的复杂度是 $O(V\sum s_i)$。二进制拆分把数量拆成：

\[ 1,2,4,\ldots,2^k,\ s_i-(1+2+\cdots+2^k), \]

任意 $0\sim s_i$ 的数量都能由这些组组合出来，于是问题转化为 01 背包，拆分组数为 $O(\log s_i)$。

C++ 模板：二进制优化¶

C++
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct Item {
    int volume;
    int value;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, V;
    cin >> n >> V;
    vector<Item> items;

    for (int i = 0, v, w, s; i < n; ++i) {
        cin >> v >> w >> s;
        for (int k = 1; k <= s; k <<= 1) {
            items.push_back({k * v, k * w});
            s -= k;
        }
        if (s > 0) {
            items.push_back({s * v, s * w});
        }
    }

    vector<int> dp(V + 1);
    for (const auto& item : items) {
        for (int j = V; j >= item.volume; --j) {
            dp[j] = max(dp[j], dp[j - item.volume] + item.value);
        }
    }
    cout << dp[V] << '\n';
}

当 $N$、$V$ 和数量范围都很大时，还可以按 j % v_i 分组，用单调队列把单种物品的转移优化为 $O(V)$。

中文模板：AcWing 5. 多重背包问题 II
练习：洛谷 P1776 宝物筛选、洛谷 P2347 砝码称重

4. 混合背包¶

模型¶

同一道题中同时出现：

s = -1：01 物品；
s = 0：完全物品；
s > 0：最多使用 s 次的多重物品。

01 与多重物品逆序更新，完全物品正序更新。多重物品继续做二进制拆分。

C++ 模板¶

C++
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, V;
    cin >> n >> V;
    vector<int> dp(V + 1);

    auto zeroOne = [&](int v, int w) {
        for (int j = V; j >= v; --j) {
            dp[j] = max(dp[j], dp[j - v] + w);
        }
    };

    auto complete = [&](int v, int w) {
        for (int j = v; j <= V; ++j) {
            dp[j] = max(dp[j], dp[j - v] + w);
        }
    };

    for (int i = 0, v, w, s; i < n; ++i) {
        cin >> v >> w >> s;
        if (s == -1) {
            zeroOne(v, w);
        } else if (s == 0) {
            complete(v, w);
        } else {
            for (int k = 1; k <= s; k <<= 1) {
                zeroOne(k * v, k * w);
                s -= k;
            }
            if (s > 0) {
                zeroOne(s * v, s * w);
            }
        }
    }

    cout << dp[V] << '\n';
}

中文模板：AcWing 7. 混合背包问题
练习：洛谷 P1833 樱花、洛谷 P1782 旅行商的背包

5. 二维费用背包¶

模型¶

每件物品同时消耗两类资源，例如重量与体积、金钱与时间。令 dp[j][k] 表示第一维容量不超过 j、第二维容量不超过 k 时的最大价值：

\[ dp_{j,k}=\max(dp_{j,k},\ dp_{j-a_i,k-b_i}+w_i). \]

若每件物品只能选一次，两维容量都要逆序。

C++ 模板¶

C++
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, V, W;
    cin >> n >> V >> W;
    vector<vector<int>> dp(V + 1, vector<int>(W + 1));

    for (int i = 0, a, b, value; i < n; ++i) {
        cin >> a >> b >> value;
        for (int j = V; j >= a; --j) {
            for (int k = W; k >= b; --k) {
                dp[j][k] = max(dp[j][k], dp[j - a][k - b] + value);
            }
        }
    }

    cout << dp[V][W] << '\n';
}

中文模板：AcWing 8. 二维费用的背包问题
练习：洛谷 P1507 NASA 的食物计划、洛谷 P1855 榨取 kkksc03

6. 分组背包¶

模型¶

物品被划分为若干组，每组最多选择一件。外层必须先枚举组；容量逆序枚举；最后枚举当前组中的物品：

\[ dp_j=\max\left(dp_j,\ \max_{k\in G_i,\ v_k\le j}(dp_{j-v_k}+w_k)\right). \]

容量放在组内物品之前，能保证同一容量状态只从上一组转移，避免同组选择多件。

C++ 模板¶

C++
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int groups, V;
    cin >> groups >> V;
    vector<int> dp(V + 1);

    for (int g = 0; g < groups; ++g) {
        int count;
        cin >> count;
        vector<pair<int, int>> items(count);
        for (auto& [v, w] : items) {
            cin >> v >> w;
        }

        for (int j = V; j >= 0; --j) {
            for (auto [v, w] : items) {
                if (j >= v) {
                    dp[j] = max(dp[j], dp[j - v] + w);
                }
            }
        }
    }

    cout << dp[V] << '\n';
}

中文模板：AcWing 9. 分组背包问题
练习：洛谷 P1757 通天之分组背包、洛谷 P5322 排兵布阵

7. 有依赖的背包¶

模型¶

选择一件物品前必须先选择它的父物品，依赖关系通常构成一棵树。对每个结点 u 做树形背包：

dp[u][j] 表示在 u 的子树中使用容量 j，并且选择 u 时的最大价值；
先把 dp[u][v[u]] 初始化为 w[u]；
逐个合并孩子，枚举给孩子分配的容量。

合并一个孩子本质上是一次分组背包：这个孩子的整棵子树可以不选，或选一个合法容量方案。

C++ 模板¶

C++
#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, V;
    cin >> n >> V;
    vector<int> volume(n), value(n);
    vector<vector<int>> children(n);
    int root = -1;

    for (int i = 0, parent; i < n; ++i) {
        cin >> volume[i] >> value[i] >> parent;
        if (parent == -1) {
            root = i;
        } else {
            children[parent - 1].push_back(i);
        }
    }

    const int NEG = numeric_limits<int>::min() / 4;
    vector<vector<int>> dp(n, vector<int>(V + 1, NEG));
    vector<int> used(n);

    function<void(int)> dfs = [&](int u) {
        if (volume[u] <= V) {
            dp[u][volume[u]] = value[u];
            used[u] = volume[u];
        }

        for (int child : children[u]) {
            dfs(child);
            vector<int> next = dp[u];

            for (int j = volume[u]; j <= min(V, used[u]); ++j) {
                if (dp[u][j] == NEG) {
                    continue;
                }
                for (int k = 1; k <= min(used[child], V - j); ++k) {
                    if (dp[child][k] != NEG) {
                        next[j + k] = max(next[j + k], dp[u][j] + dp[child][k]);
                    }
                }
            }

            used[u] = min(V, used[u] + used[child]);
            dp[u].swap(next);
        }
    };

    dfs(root);
    cout << max(0, *max_element(dp[root].begin(), dp[root].end())) << '\n';
}

该模板按“实际使用容量”记录状态，因此最终对 0..V 取最大值。若题目存在多个根，可以增加一个体积、价值均为 0 的虚根。

中文模板：AcWing 10. 有依赖的背包问题
练习：洛谷 P1064 金明的预算方案、洛谷 P2014 选课、洛谷 P1273 有线电视网

8. 背包问题求方案数¶

模型¶

方案计数有两类常见问法：

有多少种方案恰好达到某个容量；
达到最大价值的方案有多少种。

下面处理第 2 类。best[j] 表示恰好使用容量 j 时的最大价值，ways[j] 表示达到该价值的方案数。转移时：

新价值更大：覆盖最大价值与方案数；
新价值相等：累加方案数；
状态不可达：不能参与转移。

C++ 模板：最优方案数¶

C++
#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const int MOD = 1'000'000'007;
    const long long NEG = numeric_limits<long long>::min() / 4;

    int n, V;
    cin >> n >> V;
    vector<long long> best(V + 1, NEG);
    vector<int> ways(V + 1);
    best[0] = 0;
    ways[0] = 1;

    for (int i = 0, v, w; i < n; ++i) {
        cin >> v >> w;
        for (int j = V; j >= v; --j) {
            if (best[j - v] == NEG) {
                continue;
            }
            long long candidate = best[j - v] + w;
            if (candidate > best[j]) {
                best[j] = candidate;
                ways[j] = ways[j - v];
            } else if (candidate == best[j]) {
                ways[j] += ways[j - v];
                if (ways[j] >= MOD) {
                    ways[j] -= MOD;
                }
            }
        }
    }

    long long optimum = *max_element(best.begin(), best.end());
    int answer = 0;
    for (int j = 0; j <= V; ++j) {
        if (best[j] == optimum) {
            answer += ways[j];
            if (answer >= MOD) {
                answer -= MOD;
            }
        }
    }
    cout << answer << '\n';
}

若题目问“恰好装满容量 $V$ 的方案数”，则直接输出 ways[V]；若不要求最优价值，状态可以简化为 count[j] += count[j-v]。

中文模板：AcWing 11. 背包问题求方案数
练习：洛谷 P1164 小 A 点菜、洛谷 P1474 Money System

9. 背包问题求具体方案¶

模型¶

只保存最优值无法直接知道选择了哪些物品。若要求输出字典序最小的最优方案，可以反向定义：

\[ f_{i,j}=\text{从第 }i\text{ 件到第 }n\text{ 件中选择，容量不超过 }j\text{ 的最大价值}. \]

从后向前计算，再从编号 1 开始恢复。若“选”和“不选”都能达到最优值，优先选择当前编号，就能得到字典序最小的编号序列。

C++ 模板：输出字典序最小的最优方案¶

C++
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, V;
    cin >> n >> V;
    vector<int> volume(n + 1), value(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> volume[i] >> value[i];
    }

    vector<vector<int>> dp(n + 2, vector<int>(V + 1));
    for (int i = n; i >= 1; --i) {
        for (int j = 0; j <= V; ++j) {
            dp[i][j] = dp[i + 1][j];
            if (j >= volume[i]) {
                dp[i][j] = max(
                    dp[i][j],
                    dp[i + 1][j - volume[i]] + value[i]);
            }
        }
    }

    int remaining = V;
    for (int i = 1; i <= n; ++i) {
        if (remaining >= volume[i] &&
            dp[i][remaining] ==
                dp[i + 1][remaining - volume[i]] + value[i]) {
            cout << i << ' ';
            remaining -= volume[i];
        }
    }
    cout << '\n';
}

一般的方案恢复也可以保存前驱：每当状态被更优转移更新，就记录它来自哪个旧状态以及选择了哪件物品。

中文模板：AcWing 12. 背包问题求具体方案
练习：洛谷 P2066 机器分配

10. 初始化决定题意¶

同一条转移，初始化不同，含义也不同：

容量不超过上限¶

求最大价值时可以把 dp[0..V] 全部初始化为 0，表示容量有剩余也合法。

必须恰好装满¶

只令 dp[0] = 0，其余状态初始化为负无穷。这样不可达状态不会参与转移。

C++
const long long NEG = -(1LL << 60);
vector<long long> dp(V + 1, NEG);
dp[0] = 0;

若求最小值，则不可达状态应初始化为正无穷，并在加法前判断是否可达，避免溢出。

11. 高频错误清单¶

把 01 背包的容量写成正序，导致同一物品被重复使用；
把完全背包写成逆序，结果退化为每件只能选一次；
分组背包先枚举组内物品再枚举容量，导致同组选择多件；
多重背包二进制拆分后漏掉最后的余数；
“恰好装满”却把所有 dp 初始化为 0；
从负无穷状态直接做加法，引发伪可达或整数溢出；
方案计数时只记录数量、不同时记录当前最优值；
恢复字典序最小方案时顺序与 DP 定义不匹配。

12. 识别题型的顺序¶

读题时可以依次判断：

物品是否可拆分？可拆分通常是贪心的部分背包，不属于本章；
每件物品能选 0/1 次、无限次，还是有限次？
是否有多维容量、分组互斥或父子依赖？
求最大值、可行性、方案数，还是具体方案？
容量是“不超过”还是“恰好等于”？

模型、状态含义与初始化确认后，再写循环顺序，能避免绝大多数背包错误。

背包九讲：模型、状态转移与 C++ 模板¶

0. 一张表看懂循环顺序¶

1. 01 背包¶

模型¶

C++ 模板¶

2. 完全背包¶

模型¶

C++ 模板¶

3. 多重背包¶

模型¶

C++ 模板：二进制优化¶

4. 混合背包¶

模型¶

C++ 模板¶

5. 二维费用背包¶

模型¶

C++ 模板¶

6. 分组背包¶

模型¶

C++ 模板¶

7. 有依赖的背包¶

模型¶

C++ 模板¶

8. 背包问题求方案数¶

模型¶

C++ 模板：最优方案数¶

9. 背包问题求具体方案¶

模型¶

C++ 模板：输出字典序最小的最优方案¶

10. 初始化决定题意¶

容量不超过上限¶

必须恰好装满¶

11. 高频错误清单¶

12. 识别题型的顺序¶

参考资料¶